<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-34.html">previous</a></span><span>, <a href="book-Z-H-36.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_sec_5.5"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.5">5.5&nbsp;&nbsp;Compilation</a></h2><p>


<a name="%_idx_6194"></a>
The explicit-control evaluator of section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4">5.4</a> is a
register machine whose controller interprets Scheme programs.  In this
section we will see how to run Scheme programs on a register machine
whose controller is not a Scheme interpreter.<p>

<a name="%_idx_6196"></a><a name="%_idx_6198"></a>The explicit-control evaluator machine is universal -- it can carry out
any computational process that can be described in Scheme.  The
evaluator's controller orchestrates the use of its data paths to
perform the desired computation.  Thus, the evaluator's data paths are
universal: They are sufficient to perform any computation we desire,
given an appropriate controller.<a name="call_footnote_Temp_794" href="#footnote_Temp_794"><sup><small>33</small></sup></a><p>

<a name="%_idx_6200"></a><a name="%_idx_6202"></a>Commercial general-purpose computers are register machines organized
around a collection of registers and operations that constitute
an efficient and convenient universal set of data paths.
The controller for a general-purpose machine is an interpreter for
a register-machine language like the one we have been using.  This
language is called the <a name="%_idx_6204"></a><em>native language</em> of the machine, or simply
<a name="%_idx_6206"></a><em>machine language</em>.  Programs written in machine language are
sequences of instructions that use the machine's data paths.
For example, the <a name="%_idx_6208"></a>explicit-control evaluator's instruction sequence
can be thought of as a machine-language program for a general-purpose
computer rather than as the controller for a specialized interpreter
machine.<p>

<a name="%_idx_6210"></a><a name="%_idx_6212"></a>There are two common strategies for bridging the gap between
higher-level languages and register-machine languages.  The
explicit-control evaluator illustrates the
strategy of interpretation.  An interpreter written in the native
language of a machine configures the machine to execute programs
written in a language (called the <a name="%_idx_6214"></a><em>source language</em>) that may
differ from the native language of the machine performing the
evaluation.  The primitive procedures of the source language are
implemented as a library of subroutines written in the native language
of the given machine.  A program to be interpreted (called the <a name="%_idx_6216"></a><em>source program</em>) is represented as a data structure.  The interpreter
traverses this data structure, analyzing the source program.  As it
does so, it simulates the intended behavior of the source program by
calling appropriate primitive subroutines from the library.<p>


In this section, we explore the alternative strategy of <em>compilation</em>.  A compiler for a given source language and machine
translates a source program into an equivalent program (called the
<a name="%_idx_6218"></a><em>object program</em>) written in the machine's native language.  The
compiler that we implement in this section translates programs written
in Scheme into sequences of instructions to be executed using
the explicit-control evaluator machine's data paths.<a name="call_footnote_Temp_795" href="#footnote_Temp_795"><sup><small>34</small></sup></a><p>

Compared with interpretation, compilation can provide a great increase
in the efficiency of program execution, as we will explain below in
the overview of the compiler.  On the other hand, an interpreter
provides a more powerful environment for interactive program
development and debugging, because the source program being executed
is available at run time to be examined and modified.  In addition,
because the entire library of primitives is present, new programs can
be constructed and added to the system during debugging.<p>

In view of the complementary advantages of compilation and
interpretation, modern program-development environments pursue a mixed
strategy.  Lisp interpreters are generally organized so that
interpreted procedures and compiled procedures can call each other.
This enables a programmer to compile those parts of a program that are
assumed to be debugged, thus gaining the efficiency advantage of
compilation, while retaining the interpretive mode of execution for
those parts of the program that are in the flux of interactive
development and debugging.  In
section&nbsp;<a href="#%_sec_5.5.7">5.5.7</a>, after we have implemented
the compiler, we will show how to interface it with our interpreter to
produce an integrated interpreter-compiler development system.<p>

<a name="%_sec_Temp_796"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_796">An overview of the compiler</a></h4><p>

<a name="%_idx_6224"></a><a name="%_idx_6226"></a>
Our compiler is much like our interpreter, both in its structure and in
the function it performs.  Accordingly, the mechanisms used by the
compiler for analyzing expressions will be similar to those used by
the interpreter.  Moreover, to make it easy to interface compiled and
interpreted code, we will design the compiler to generate code that
obeys the same conventions of <a name="%_idx_6228"></a>register usage as the interpreter: The
environment will be kept in the <tt>env</tt> register, argument lists
will be accumulated in <tt>argl</tt>, a procedure to be applied will be
in <tt>proc</tt>, procedures will return their answers in <tt>val</tt>,
and the location to which a procedure should return will be kept in
<tt>continue</tt>.
In general, the compiler translates a source program into an object
program that performs essentially the same register operations as
would the interpreter in evaluating the same source program.<p>

This description suggests a strategy for implementing a rudimentary
compiler: We traverse the expression in the same way the
interpreter does.  When we encounter a register instruction that the
interpreter would perform in evaluating the expression, we do not
execute the instruction but instead accumulate it into a sequence.  The
resulting sequence of instructions will be the object code.  Observe
the <a name="%_idx_6230"></a><a name="%_idx_6232"></a>efficiency advantage of compilation over interpretation.  Each
time the interpreter evaluates an expression -- for example,
<tt>(f 84 96)</tt> -- it performs the work of
classifying the expression (discovering that this
is a procedure application) and testing for the end of the operand list
(discovering that there are two operands).  With a
compiler, the expression is analyzed only once, when the
instruction sequence is generated at compile time.  The object code
produced by the compiler contains only the instructions that evaluate
the operator and the two operands, assemble the argument list,
and apply the procedure (in <tt>proc</tt>) to the arguments (in <tt>argl</tt>).<p>


<a name="%_idx_6234"></a>This is the same kind of optimization we implemented in the
analyzing evaluator of section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>.
But there are further opportunities to gain efficiency in compiled code.
As the interpreter runs, it follows a process that must be applicable
to any expression in the language.  In contrast, a given segment of
compiled code is meant to execute some particular expression.  This
can make a big difference, for example in the use of the stack to
save registers.  When the interpreter evaluates an expression, it must
be prepared for any contingency.  Before evaluating a subexpression,
the interpreter saves all
registers that will be needed later, because
the subexpression might require an arbitrary evaluation.
A compiler, on the other hand, can exploit the structure of the
particular expression it is processing to generate code that avoids
unnecessary stack operations.<p>

As a case in point, consider the combination <tt>(f 84 96)</tt>.  Before
the interpreter evaluates the operator of the combination, it prepares
for this evaluation by saving the registers containing the operands
and the environment, whose values will be needed later.  The
interpreter then evaluates the operator to obtain the result in <tt>val</tt>, restores the saved registers, and finally moves the result from
<tt>val</tt> to <tt>proc</tt>.  However, in the particular expression we are
dealing with, the operator is the symbol <tt>f</tt>, whose evaluation is
accomplished by the machine operation <tt>lookup-variable-value</tt>,
which does not alter any registers.  The compiler that we implement in
this section will take advantage of this fact and generate code that
evaluates the operator using the instruction
<p><p><tt>(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;f)&nbsp;(reg&nbsp;env))<br>
</tt><p><p>
This code not only avoids the unnecessary saves and
restores but also assigns the value of the lookup directly to
<tt>proc</tt>, whereas the interpreter would obtain the result in <tt>val</tt>
and then move this to <tt>proc</tt>.<p>


A compiler can also optimize access to the environment.  Having
analyzed the code, the compiler can in many cases know in which frame
a particular variable will be located and access that frame directly,
rather than performing the <tt>lookup-variable-value</tt> search.  We
will discuss how to implement such variable access in
section&nbsp;<a href="#%_sec_5.5.6">5.5.6</a>.  Until then, however, we will
focus on the kind of register and stack optimizations described above.
There are many other optimizations that can be performed by a
compiler, such as coding primitive operations ``in line'' instead of
using a general <tt>apply</tt> mechanism (see
exercise&nbsp;<a href="#%_thm_5.38">5.38</a>); but we will not emphasize these here.
Our main goal in this section is to illustrate the compilation process
in a simplified (but still interesting) context.<p>

<a name="%_sec_5.5.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.1">5.5.1&nbsp;&nbsp;Structure of the Compiler</a></h3><p>


<a name="%_idx_6236"></a>
<a name="%_idx_6238"></a>In section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a> we modified our original
metacircular interpreter to separate analysis from execution.  We
analyzed each expression to produce an execution procedure that took
an environment as argument and performed the required operations.  In
our compiler, we will do essentially the same analysis.  Instead of
producing execution procedures, however, we will generate sequences of
instructions to be run by our register machine.<p>


The procedure <tt>compile</tt> is the top-level dispatch in the compiler.
It corresponds to the <tt>eval</tt> procedure of
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, the <tt>analyze</tt> procedure of
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>, and the <tt>eval-dispatch</tt>
entry point of the explicit-control-evaluator in
section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>.
The compiler, like the interpreters, uses the <a name="%_idx_6240"></a>expression-syntax
procedures defined in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>.<a name="call_footnote_Temp_797" href="#footnote_Temp_797"><sup><small>35</small></sup></a>
<tt>Compile</tt> performs a case
analysis on the syntactic type of the expression to be compiled.  For
each type of expression, it dispatches to a specialized <a name="%_idx_6242"></a><em>code
generator</em>:<p>

<p><p><tt><a name="%_idx_6244"></a>(define&nbsp;(compile&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(cond&nbsp;((self-evaluating?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-self-evaluating&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((quoted?&nbsp;exp)&nbsp;(compile-quoted&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((variable?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-variable&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((assignment?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-assignment&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((definition?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-definition&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((if?&nbsp;exp)&nbsp;(compile-if&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((lambda?&nbsp;exp)&nbsp;(compile-lambda&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((begin?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-sequence&nbsp;(begin-actions&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;target<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((cond?&nbsp;exp)&nbsp;(compile&nbsp;(cond-&gt;if&nbsp;exp)&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((application?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-application&nbsp;exp&nbsp;target&nbsp;linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;&quot;Unknown&nbsp;expression&nbsp;type&nbsp;--&nbsp;COMPILE&quot;&nbsp;exp))))<br>
</tt><p><p><p>


<a name="%_sec_Temp_798"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_798">Targets and linkages</a></h4><p>

<a name="%_idx_6246"></a><tt>Compile</tt> and the code generators that it calls take two arguments
in addition to the expression to compile.  There is a <a name="%_idx_6248"></a><em>target</em>,
which specifies the register in which the compiled code is to return
the value of the expression.  There is also a <a name="%_idx_6250"></a><em>linkage
descriptor</em>, which describes how the code resulting from the
compilation of the expression should proceed when it has finished its
execution.  The linkage descriptor can require that the code do one of
the following three things:<p>

<p><ul>
<li>continue at the next instruction in sequence (this is
<a name="%_idx_6252"></a>specified by the linkage descriptor <tt>next</tt>),<p>

<li>return from the procedure being compiled (this is specified
<a name="%_idx_6254"></a>by the linkage descriptor <tt>return</tt>), or<p>

<li>jump to a named entry point (this is specified by using the
designated label as the linkage descriptor).
</ul><p><p>

For example, compiling the expression <tt>5</tt> (which is
self-evaluating) with a target of the <tt>val</tt> register and a
linkage of <tt>next</tt> should produce the instruction<p>

<p><p><tt>(assign&nbsp;val&nbsp;(const&nbsp;5))<br>
</tt><p><p>
Compiling the same expression with a linkage of <tt>return</tt> should
produce the instructions<p>

<p><p><tt>(assign&nbsp;val&nbsp;(const&nbsp;5))<br>
(goto&nbsp;(reg&nbsp;continue))<br>
</tt><p><p>
In the first case, execution will continue with the next instruction
in the sequence. In the second case, we will return from a procedure
call.  In both cases, the value of the expression will be placed into
the target <tt>val</tt> register.<p>

<a name="%_sec_Temp_799"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_799">Instruction sequences and stack usage</a></h4><p>

<p>

<a name="%_idx_6256"></a><a name="%_idx_6258"></a>Each code generator returns an <em>instruction sequence</em> containing
the object code it has generated for the expression.  Code generation
for a compound expression is accomplished by combining the output from
simpler code generators for component expressions, just as
evaluation of a compound expression is accomplished by evaluating the
component expressions.<p>


The simplest method for combining instruction sequences is a procedure
<a name="%_idx_6260"></a>called <tt>append-instruction-sequences</tt>.  It takes as arguments any
number of instruction sequences that are to be executed sequentially;
it appends them and returns the combined sequence.  That is, if
&lt;<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>&gt; and &lt;<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>&gt; are sequences of instructions, then
evaluating
<p><p><tt>(append-instruction-sequences&nbsp;&lt;<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>&gt;&nbsp;&lt;<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>&gt;)<br>
</tt><p><p>
produces the sequence
<p><p><tt>&lt;<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>&gt;<br>
&lt;<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>&gt;<br>
</tt><p><p><p>

<a name="%_idx_6262"></a>Whenever registers might need to be saved, the compiler's code generators use
<a name="%_idx_6264"></a><tt>preserving</tt>, which is a more subtle method for combining
instruction sequences.  <tt>Preserving</tt> takes three arguments: a set
of registers and two instruction sequences that are to be executed
sequentially.  It appends the sequences in such a way that the
contents of each register in the set is preserved over the execution
of the first sequence, if this is needed for the execution of the
second sequence.  That is, if the first sequence modifies the register
and the second sequence actually needs the register's original
contents, then <tt>preserving</tt> wraps a <tt>save</tt> and a <tt>restore</tt>
of the register around the first sequence before appending the
sequences.  Otherwise, <tt>preserving</tt> simply returns the appended
instruction sequences.  Thus, for example,
<p><p><tt>(preserving&nbsp;(list&nbsp;&lt;<em><em>r</em><em>e</em><em>g</em><sub>1</sub></em>&gt;&nbsp;&lt;<em><em>r</em><em>e</em><em>g</em><sub>2</sub></em>&gt;)&nbsp;&lt;<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>&gt;&nbsp;&lt;<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>&gt;)<br>
</tt><p><p>
produces one of the following four sequences of instructions, depending on how
&lt;<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>&gt; and &lt;<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>&gt; use &lt;<em><em>r</em><em>e</em><em>g</em><sub>1</sub></em>&gt; and &lt;<em><em>r</em><em>e</em><em>g</em><sub>2</sub></em>&gt;:<p>

<p><p><p><div align=left><img src="ch5-Z-G-9.gif" border="0"></div><p><p>

By using <tt>preserving</tt> to combine instruction sequences the
compiler avoids unnecessary stack operations.  This also isolates the
details of whether or not to generate <tt>save</tt> and <tt>restore</tt>
instructions within the <tt>preserving</tt> procedure, separating them
from the concerns that arise in writing each of the individual code
generators.
In fact no <tt>save</tt> or <tt>restore</tt> instructions are explicitly
produced by the code generators.<p>

In principle, we could represent an instruction sequence simply as a
list of instructions.  <tt>Append-instruction-sequences</tt> could then
combine instruction sequences by performing an ordinary list <tt>append</tt>.  However, <tt>preserving</tt> would then be a complex operation,
because it would have to analyze each instruction sequence to
determine how the sequence uses its registers.  <tt>Preserving</tt>
would be inefficient as well as complex, because it would have to
analyze each of its instruction sequence arguments, even though these
sequences might themselves have been constructed by calls to <tt>preserving</tt>, in which case their parts would have already been
analyzed.  To avoid such repetitious analysis we will associate with each
instruction sequence some information about its register use.
When we construct a basic instruction sequence we
will provide this information explicitly,
and the procedures that combine instruction sequences will derive
register-use information for the combined sequence from the
information associated with the component sequences.<p>

An instruction sequence will contain three pieces of information:
<p><ul>
<li>the set of registers that must be initialized before the
instructions in the sequence are executed (these registers are said to
be <em>needed</em> by the sequence),<p>

<li>the set of registers whose values are modified by the
instructions in the sequence, and<p>

<li>the actual instructions (also called <em>statements</em>) in
the sequence.
</ul><p><p>

We will represent an instruction sequence as a list of its three
parts.  The constructor for instruction sequences is thus<p>

<p><p><tt><a name="%_idx_6266"></a>(define&nbsp;(make-instruction-sequence&nbsp;needs&nbsp;modifies&nbsp;statements)<br>
&nbsp;&nbsp;(list&nbsp;needs&nbsp;modifies&nbsp;statements))<br>
</tt><p><p><p>

For example, the two-instruction sequence that looks up the value of
the variable <tt>x</tt> in the current environment, assigns the result
to <tt>val</tt>, and then returns, requires registers <tt>env</tt> and <tt>continue</tt> to have been initialized, and modifies register <tt>val</tt>.
This sequence would therefore be constructed as<p>

<p><p><tt>(make-instruction-sequence&nbsp;'(env&nbsp;continue)&nbsp;'(val)<br>
&nbsp;'((assign&nbsp;val<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;x)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;continue))))<br>
</tt><p><p><p>

We sometimes need to construct an instruction sequence with no statements:
<p><p><tt><a name="%_idx_6268"></a>(define&nbsp;(empty-instruction-sequence)<br>
&nbsp;&nbsp;(make-instruction-sequence&nbsp;'()&nbsp;'()&nbsp;'()))<br>
</tt><p><p>
<p>

The procedures for combining instruction sequences are shown in
section&nbsp;<a href="#%_sec_5.5.4">5.5.4</a>.<p>

<p><a name="%_thm_5.31"></a>
<b>Exercise 5.31.</b>&nbsp;&nbsp;<a name="%_idx_6270"></a><a name="%_idx_6272"></a>In evaluating a procedure application, the explicit-control evaluator
always saves and restores
the <tt>env</tt> register around the evaluation of the operator, saves and
restores <tt>env</tt> around the evaluation of each operand (except the
final one), saves and restores <tt>argl</tt> around the evaluation of each
operand, and saves and restores <tt>proc</tt> around the evaluation of the
operand sequence.  For each of the following combinations, say which
of these <tt>save</tt> and <tt>restore</tt> operations are superfluous and
thus could be eliminated by the compiler's <tt>preserving</tt> mechanism:<p>

<p><p><tt>(f&nbsp;'x&nbsp;'y)<br>
<br>
((f)&nbsp;'x&nbsp;'y)<br>
<br>
(f&nbsp;(g&nbsp;'x)&nbsp;y)<br>
<br>
(f&nbsp;(g&nbsp;'x)&nbsp;'y)<br>
</tt><p><p>
<p><p>

<p><a name="%_thm_5.32"></a>
<b>Exercise 5.32.</b>&nbsp;&nbsp;<a name="%_idx_6274"></a><a name="%_idx_6276"></a>Using the <tt>preserving</tt> mechanism, the compiler will avoid saving
and restoring <tt>env</tt> around the evaluation of the operator of a
combination in the case where the operator is a symbol.  We could also
build such optimizations into the evaluator.  Indeed, the
explicit-control evaluator of section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4">5.4</a> already
performs a similar optimization, by treating combinations with no
operands as a special case.<p>

<p><p>a. Extend the explicit-control evaluator to recognize as a separate class
of expressions combinations whose operator is a symbol, and to take
advantage of this fact in evaluating such expressions.<p>

<p><p>b. Alyssa P. Hacker suggests that by extending the evaluator to recognize
more and more special cases we could incorporate all the compiler's
optimizations, and that this would eliminate the advantage of compilation
altogether.  What do you think of this idea?
<p><p>

<a name="%_sec_5.5.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.2">5.5.2&nbsp;&nbsp;Compiling Expressions</a></h3><p>

In this section and the next we implement the code generators to which the <tt>compile</tt> procedure dispatches.<p>

<a name="%_sec_Temp_802"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_802">Compiling linkage code</a></h4><p>

<a name="%_idx_6278"></a>In general, the output of each code generator will end with
instructions -- generated by the procedure <tt>compile-linkage</tt> -- that
implement the required linkage.  If the linkage is <tt>return</tt> then
we must generate the instruction <tt>(goto (reg continue))</tt>.  This
needs the <tt>continue</tt> register and does not modify any registers.
If the linkage is <tt>next</tt>, then we needn't include any additional
instructions.  Otherwise, the linkage is a label, and we generate a
<tt>goto</tt> to that label, an instruction that does not need or modify
any registers.<a name="call_footnote_Temp_803" href="#footnote_Temp_803"><sup><small>36</small></sup></a><p>


<p><p><tt><a name="%_idx_6292"></a>(define&nbsp;(compile-linkage&nbsp;linkage)<br>
&nbsp;&nbsp;(cond&nbsp;((eq?&nbsp;linkage&nbsp;'return)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(continue)&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'((goto&nbsp;(reg&nbsp;continue)))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((eq?&nbsp;linkage&nbsp;'next)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(empty-instruction-sequence))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'()&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((goto&nbsp;(label&nbsp;,linkage)))))))<br>
</tt><p><p>
The linkage code is appended to an instruction sequence by <tt>preserving</tt>
the <tt>continue</tt> register, since a <tt>return</tt> linkage will
require the <tt>continue</tt> register:
If the given instruction sequence modifies <tt>continue</tt> and the
linkage code needs it, <tt>continue</tt> will be saved and restored.<p>


<p><p><tt><a name="%_idx_6294"></a>(define&nbsp;(end-with-linkage&nbsp;linkage&nbsp;instruction-sequence)<br>
&nbsp;&nbsp;(preserving&nbsp;'(continue)<br>
&nbsp;&nbsp;&nbsp;instruction-sequence<br>
&nbsp;&nbsp;&nbsp;(compile-linkage&nbsp;linkage)))<br>
</tt><p><p><p>

<p>

<a name="%_sec_Temp_804"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_804">Compiling simple expressions</a></h4><p>

<a name="%_idx_6296"></a><a name="%_idx_6298"></a><a name="%_idx_6300"></a>The code generators for self-evaluating expressions,
quotations, and variables construct instruction
sequences that assign the required value to the target register
and then proceed as specified by the linkage descriptor.<p>


<p><p><tt><a name="%_idx_6302"></a>(define&nbsp;(compile-self-evaluating&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'()&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;,target&nbsp;(const&nbsp;,exp))))))<br>
<a name="%_idx_6304"></a>(define&nbsp;(compile-quoted&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'()&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;,target&nbsp;(const&nbsp;,(text-of-quotation&nbsp;exp)))))))<br>
<a name="%_idx_6306"></a>(define&nbsp;(compile-variable&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(env)&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;,target<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;lookup-variable-value)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;,exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))))))<br>
</tt><p><p>
All these assignment instructions modify the target register,
and the one that looks up a variable needs the <tt>env</tt> register.<p>

<a name="%_idx_6308"></a><a name="%_idx_6310"></a>Assignments and definitions are handled much as they are in the
interpreter.  We recursively generate code that computes the value to
be assigned to the variable, and append to it a two-instruction
sequence that actually sets or defines the variable and assigns the
value of the whole expression (the symbol <tt>ok</tt>) to the target
register.  The recursive compilation has target <tt>val</tt> and linkage
<tt>next</tt> so that the code will put its result into <tt>val</tt> and
continue with the code that is appended after it.  The appending is
done preserving <tt>env</tt>, since the environment is needed for setting
or defining the variable and the code for the variable value could be
the compilation of a complex expression that might modify the
registers in arbitrary ways.<p>

<p><p><tt><a name="%_idx_6312"></a>(define&nbsp;(compile-assignment&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((var&nbsp;(assignment-variable&nbsp;exp))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(get-value-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;(assignment-value&nbsp;exp)&nbsp;'val&nbsp;'next)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;get-value-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(env&nbsp;val)&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((perform&nbsp;(op&nbsp;set-variable-value!)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;,var)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;val)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;,target&nbsp;(const&nbsp;ok))))))))<br>
<a name="%_idx_6314"></a>(define&nbsp;(compile-definition&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((var&nbsp;(definition-variable&nbsp;exp))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(get-value-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;(definition-value&nbsp;exp)&nbsp;'val&nbsp;'next)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;get-value-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(env&nbsp;val)&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((perform&nbsp;(op&nbsp;define-variable!)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;,var)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;val)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;,target&nbsp;(const&nbsp;ok))))))))<br>
</tt><p><p>
The appended two-instruction sequence requires <tt>env</tt> and <tt>val</tt>
and modifies the target.  Note that although we preserve <tt>env</tt> for
this sequence, we do not preserve <tt>val</tt>, because the <tt>get-value-code</tt> is designed to explicitly place its result in <tt>val</tt> for use by this sequence.
(In fact, if we did preserve <tt>val</tt>, we would
have a bug, because this would cause the previous contents of <tt>val</tt> to be restored right after the <tt>get-value-code</tt> is run.)<p>

<a name="%_sec_Temp_805"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_805">Compiling conditional expressions</a></h4><p>

<a name="%_idx_6316"></a>The code for an <tt>if</tt> expression
compiled with a given target and linkage has the form<p>

<p><p><tt>&nbsp;&lt;<em>compilation&nbsp;of&nbsp;predicate,&nbsp;target&nbsp;<tt>val</tt>,&nbsp;linkage&nbsp;<tt>next</tt></em>&gt;<br>
&nbsp;(test&nbsp;(op&nbsp;false?)&nbsp;(reg&nbsp;val))<br>
&nbsp;(branch&nbsp;(label&nbsp;false-branch))<br>
true-branch<br>
&nbsp;&lt;<em>compilation&nbsp;of&nbsp;consequent&nbsp;with&nbsp;given&nbsp;target&nbsp;and&nbsp;given&nbsp;linkage&nbsp;or&nbsp;<tt>after-if</tt></em>&gt;<br>
false-branch<br>
&nbsp;&lt;<em>compilation&nbsp;of&nbsp;alternative&nbsp;with&nbsp;given&nbsp;target&nbsp;and&nbsp;linkage</em>&gt;<br>
after-if<br>
</tt><p><p><p>

To generate this code, we compile the predicate, consequent,
and alternative, and combine the resulting code with instructions
to test the predicate result and with newly generated labels
to mark the true and false branches and the end of the conditional.<a name="call_footnote_Temp_806" href="#footnote_Temp_806"><sup><small>37</small></sup></a>
In this arrangement of code, we must branch around the true branch
if the test is false.  The only slight complication is in how the
linkage for the true branch should be handled.  If the linkage for the
conditional is <tt>return</tt> or a label, then the true and false
branches will both use this same linkage.  If the linkage is <tt>next</tt>, the true branch ends with a jump around the code for the false
branch to the label at the end of the conditional.<p>



<p><p><tt><a name="%_idx_6324"></a>(define&nbsp;(compile-if&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((t-branch&nbsp;(make-label&nbsp;'true-branch))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(f-branch&nbsp;(make-label&nbsp;'false-branch))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(after-if&nbsp;(make-label&nbsp;'after-if)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((consequent-linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(eq?&nbsp;linkage&nbsp;'next)&nbsp;after-if&nbsp;linkage)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((p-code&nbsp;(compile&nbsp;(if-predicate&nbsp;exp)&nbsp;'val&nbsp;'next))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(c-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if-consequent&nbsp;exp)&nbsp;target&nbsp;consequent-linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(a-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;(if-alternative&nbsp;exp)&nbsp;target&nbsp;linkage)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env&nbsp;continue)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(val)&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((test&nbsp;(op&nbsp;false?)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(branch&nbsp;(label&nbsp;,f-branch))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(parallel-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences&nbsp;t-branch&nbsp;c-code)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences&nbsp;f-branch&nbsp;a-code))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;after-if))))))<br>
</tt><p><p>
<tt>Env</tt> is preserved around the predicate code because it could be needed by
the true and false branches, and <tt>continue</tt> is preserved because it could
be needed by the linkage code in those branches.  The code for the true and
false branches (which are not executed sequentially) is appended using a
special combiner <tt>parallel-instruction-sequences</tt> described in
section&nbsp;<a href="#%_sec_5.5.4">5.5.4</a>.<p>


Note that <tt>cond</tt> is a derived expression, so all that the
compiler needs to do handle it is to apply the <tt>cond-&gt;if</tt>
transformer (from section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>) and
compile the resulting <tt>if</tt> expression.<p>

<a name="%_sec_Temp_807"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_807">Compiling sequences</a></h4><p>

<a name="%_idx_6326"></a>The compilation of sequences (from procedure bodies or explicit <tt>begin</tt> expressions) parallels their evaluation.  Each expression of the
sequence is compiled -- the last expression with the linkage specified
for the sequence, and the other expressions with linkage <tt>next</tt>
(to execute the rest of the sequence).
The instruction sequences for the individual expressions are appended
to form a single instruction sequence, such that <tt>env</tt> (needed for
the rest of the sequence) and <tt>continue</tt> (possibly needed for the
linkage at the end of the sequence) are preserved.<p>

<p><p><tt><a name="%_idx_6328"></a>(define&nbsp;(compile-sequence&nbsp;seq&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(if&nbsp;(last-exp?&nbsp;seq)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;(first-exp&nbsp;seq)&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env&nbsp;continue)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;(first-exp&nbsp;seq)&nbsp;target&nbsp;'next)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-sequence&nbsp;(rest-exps&nbsp;seq)&nbsp;target&nbsp;linkage))))<br>
</tt><p><p><p>

<a name="%_sec_Temp_808"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_808">Compiling <tt>lambda</tt> expressions</a></h4><p>

<a name="%_idx_6330"></a><tt>Lambda</tt> expressions construct procedures.
The object code for a <tt>lambda</tt> expression must have the form<p>

<p><p><tt>&lt;<em>construct&nbsp;procedure&nbsp;object&nbsp;and&nbsp;assign&nbsp;it&nbsp;to&nbsp;target&nbsp;register</em>&gt;<br>
&lt;<em>linkage</em>&gt;<br>
</tt><p><p>
When we compile the <tt>lambda</tt> expression, we also generate the code for the
procedure body.  Although the body won't be executed at the time of procedure
construction, it is convenient to insert it into the object code right after
the code for the <tt>lambda</tt>.  If the linkage for the <tt>lambda</tt> expression
is a label or <tt>return</tt>, this is fine.  But if the linkage is <tt>next</tt>,
we will need to skip around the code for the procedure body by using a linkage
that jumps to a label that is inserted after the body.  The object code thus
has the form<p>

<p><p><tt>&nbsp;&lt;<em>construct&nbsp;procedure&nbsp;object&nbsp;and&nbsp;assign&nbsp;it&nbsp;to&nbsp;target&nbsp;register</em>&gt;<br>
&nbsp;&lt;<em>code&nbsp;for&nbsp;given&nbsp;linkage</em>&gt;<em>or</em>&nbsp;<tt>(goto&nbsp;(label&nbsp;after-lambda))</tt><br>
&nbsp;&lt;<em>compilation&nbsp;of&nbsp;procedure&nbsp;body</em>&gt;<br>
after-lambda<br>
</tt><p><p><p>

<tt>Compile-lambda</tt> generates the code for constructing the procedure
object followed by the code for the procedure body.
The procedure object will be constructed at run time by combining
the current environment (the environment at the point of definition)
with the entry point to the compiled procedure body (a newly generated
label).<a name="call_footnote_Temp_809" href="#footnote_Temp_809"><sup><small>38</small></sup></a><p>

<p><p><tt><a name="%_idx_6340"></a>(define&nbsp;(compile-lambda&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((proc-entry&nbsp;(make-label&nbsp;'entry))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(after-lambda&nbsp;(make-label&nbsp;'after-lambda)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((lambda-linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(eq?&nbsp;linkage&nbsp;'next)&nbsp;after-lambda&nbsp;linkage)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(tack-on-instruction-sequence<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(end-with-linkage&nbsp;lambda-linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(env)&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;,target<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;make-compiled-procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(label&nbsp;,proc-entry)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env)))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-lambda-body&nbsp;exp&nbsp;proc-entry))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;after-lambda))))<br>
</tt><p><p>
<tt>Compile-lambda</tt> uses the special combiner <tt>tack-on-instruction-sequence</tt>
(section&nbsp;<a href="#%_sec_5.5.4">5.5.4</a>) rather than <tt>append-instruction-sequences</tt> to append the procedure body to the <tt>lambda</tt>
expression code, because the body is not part of the sequence of instructions
that will be executed when the combined sequence is entered; rather, it is in
the sequence only because that was a convenient place to put it.<p>


<tt>Compile-lambda-body</tt> constructs the code for the body of the
procedure.  This code begins with a label for the entry point.  Next
come instructions that will cause the run-time evaluation environment
to switch to the correct environment for evaluating the procedure
body -- namely, the definition environment of the procedure, extended
to include the bindings of the formal parameters to the arguments with
which the procedure is called.  After this comes the code for the
sequence of expressions that makes up the procedure body.
The sequence is compiled with linkage <tt>return</tt> and target <tt>val</tt>
so that it will end by returning from the procedure with the
procedure result in <tt>val</tt>.<p>

<p><p><tt>(define&nbsp;(compile-lambda-body&nbsp;exp&nbsp;proc-entry)<br>
&nbsp;&nbsp;(let&nbsp;((formals&nbsp;(lambda-parameters&nbsp;exp)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(env&nbsp;proc&nbsp;argl)&nbsp;'(env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`(,proc-entry<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;compiled-procedure-env)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;env<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;extend-environment)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;,formals)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-sequence&nbsp;(lambda-body&nbsp;exp)&nbsp;'val&nbsp;'return))))<br>
</tt><p><p><p>

<a name="%_sec_5.5.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.3">5.5.3&nbsp;&nbsp;Compiling Combinations</a></h3><p>


<a name="%_idx_6342"></a><a name="%_idx_6344"></a>
The essence of the compilation process is the compilation of procedure
applications.
The code for a combination compiled with a given target and linkage
has the form
<p><p><tt>&lt;<em>compilation&nbsp;of&nbsp;operator,&nbsp;target&nbsp;<tt>proc</tt>,&nbsp;linkage&nbsp;<tt>next</tt></em>&gt;<br>
&lt;<em>evaluate&nbsp;operands&nbsp;and&nbsp;construct&nbsp;argument&nbsp;list&nbsp;in&nbsp;<tt>argl</tt></em>&gt;<br>
&lt;<em>compilation&nbsp;of&nbsp;procedure&nbsp;call&nbsp;with&nbsp;given&nbsp;target&nbsp;and&nbsp;linkage</em>&gt;<br>
</tt><p><p>
The registers <tt>env</tt>, <tt>proc</tt>, and <tt>argl</tt> may have to be
saved and restored during evaluation of the operator and operands.
Note that this is the only place in the compiler where a target other
than <tt>val</tt> is specified.<p>

The required code is generated by <tt>compile-application</tt>.  This
recursively compiles the operator, to produce code that puts the
procedure to be applied into <tt>proc</tt>, and compiles the operands, to
produce code that evaluates the individual operands of the
application.  The instruction sequences for the operands are combined
(by <tt>construct-arglist</tt>) with code that constructs the list of
arguments in <tt>argl</tt>, and the resulting argument-list code is
combined with the procedure code and the code that performs the
procedure call (produced by <tt>compile-procedure-call</tt>).  In
appending the code sequences, the <tt>env</tt> register must be preserved
around the evaluation of the operator (since evaluating the operator
might modify <tt>env</tt>, which will be needed to evaluate the
operands), and the <tt>proc</tt> register must be preserved around the
construction of the argument list (since evaluating the operands might
modify <tt>proc</tt>, which will be needed for the actual procedure
application).  <tt>Continue</tt> must also be preserved throughout, since
it is needed for the linkage in the procedure call.<p>

<p><p><tt><a name="%_idx_6346"></a>(define&nbsp;(compile-application&nbsp;exp&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((proc-code&nbsp;(compile&nbsp;(operator&nbsp;exp)&nbsp;'proc&nbsp;'next))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(operand-codes<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(map&nbsp;(lambda&nbsp;(operand)&nbsp;(compile&nbsp;operand&nbsp;'val&nbsp;'next))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(operands&nbsp;exp))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env&nbsp;continue)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;proc-code<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(proc&nbsp;continue)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(construct-arglist&nbsp;operand-codes)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-procedure-call&nbsp;target&nbsp;linkage)))))<br>
</tt><p><p><p>

The code to construct the argument list will evaluate each operand into
<tt>val</tt> and then <tt>cons</tt> that value onto the argument list being
accumulated in <tt>argl</tt>.
Since we <tt>cons</tt> the arguments onto <tt>argl</tt> in sequence, we must
start with the last argument and end with the first, so that the
arguments will appear in order from first to last in the resulting list.
Rather than waste an instruction by initializing <tt>argl</tt> to the empty list
to set up for this sequence of evaluations,
we make the first code sequence construct the initial <tt>argl</tt>.
The general form of the argument-list construction is thus as follows:<p>

<p><p><tt>&lt;<em>compilation&nbsp;of&nbsp;last&nbsp;operand,&nbsp;targeted&nbsp;to&nbsp;<tt>val</tt></em>&gt;<br>
(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&lt;<em>compilation&nbsp;of&nbsp;next&nbsp;operand,&nbsp;targeted&nbsp;to&nbsp;<tt>val</tt></em>&gt;<br>
(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
<tt>...</tt>&lt;<em>compilation&nbsp;of&nbsp;first&nbsp;operand,&nbsp;targeted&nbsp;to&nbsp;<tt>val</tt></em>&gt;<br>
(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
</tt><p><p>
<tt>Argl</tt> must be preserved around each operand evaluation except
the first (so that arguments accumulated so far won't be lost), and
<tt>env</tt> must be preserved around each operand evaluation
except the last (for use by subsequent operand evaluations).<p>

Compiling this argument code is a bit tricky, because of
the special treatment of the first operand to be evaluated and the
need to preserve <tt>argl</tt> and <tt>env</tt> in different places.
The <tt>construct-arglist</tt> procedure takes as arguments the code that
evaluates the individual operands.  If there are no operands at all, it simply
emits the instruction<p>

<p><p><tt>(assign&nbsp;argl&nbsp;(const&nbsp;()))<br>
</tt><p><p>
Otherwise, <tt>construct-arglist</tt> creates code that initializes <tt>argl</tt> with the last argument, and appends code that evaluates
the rest of the arguments and adjoins them to <tt>argl</tt> in
succession.  In order to process the arguments from last to
first, we must reverse the list of operand code sequences from the order
supplied by <tt>compile-application</tt>.<p>

<p><p><tt><a name="%_idx_6348"></a>(define&nbsp;(construct-arglist&nbsp;operand-codes)<br>
&nbsp;&nbsp;(let&nbsp;((operand-codes&nbsp;(reverse&nbsp;operand-codes)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(null?&nbsp;operand-codes)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'()&nbsp;'(argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'((assign&nbsp;argl&nbsp;(const&nbsp;()))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((code-to-get-last-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(car&nbsp;operand-codes)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(val)&nbsp;'(argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'((assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val)))))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(null?&nbsp;(cdr&nbsp;operand-codes))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;code-to-get-last-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;code-to-get-last-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(code-to-get-rest-args<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cdr&nbsp;operand-codes))))))))<br>
(define&nbsp;(code-to-get-rest-args&nbsp;operand-codes)<br>
&nbsp;&nbsp;(let&nbsp;((code-for-next-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(car&nbsp;operand-codes)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(val&nbsp;argl)&nbsp;'(argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'((assign&nbsp;argl<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl)))))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(null?&nbsp;(cdr&nbsp;operand-codes))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;code-for-next-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;'(env)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;code-for-next-arg<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(code-to-get-rest-args&nbsp;(cdr&nbsp;operand-codes))))))<br>
</tt><p><p><p>

<a name="%_sec_Temp_810"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_810">Applying procedures</a></h4><p>

After evaluating the elements of a combination, the compiled code must
apply the procedure in <tt>proc</tt> to the arguments in <tt>argl</tt>.  The
code performs essentially the same dispatch as the <tt>apply</tt> procedure in the
metacircular evaluator of section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> or the
<tt>apply-dispatch</tt> entry point in the explicit-control evaluator of
section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>.  It checks whether the
procedure to be applied is a primitive procedure or a compiled
procedure.  For a primitive procedure, it uses <tt>apply-primitive-procedure</tt>; we will see shortly how it handles
compiled procedures.  The procedure-application code has the following
form:<p>

<p><p><tt>&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;(branch&nbsp;(label&nbsp;primitive-branch))<br>
compiled-branch<br>
&nbsp;&lt;<em>code&nbsp;to&nbsp;apply&nbsp;compiled&nbsp;procedure&nbsp;with&nbsp;given&nbsp;target&nbsp;and&nbsp;appropriate&nbsp;linkage</em>&gt;<br>
primitive-branch<br>
&nbsp;(assign&nbsp;&lt;<em>target</em>&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;apply-primitive-procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;argl))<br>
&nbsp;&lt;<em>linkage</em>&gt;<br>
after-call<br>
</tt><p><p>
Observe that the compiled branch must skip around the primitive
branch.  Therefore, if the linkage for the original procedure call was
<tt>next</tt>, the compound branch must use a linkage that jumps to a
label that is inserted after the primitive branch.  (This is similar
to the linkage used for the true branch in <tt>compile-if</tt>.)<p>

<p><p><tt><a name="%_idx_6350"></a>(define&nbsp;(compile-procedure-call&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(let&nbsp;((primitive-branch&nbsp;(make-label&nbsp;'primitive-branch))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compiled-branch&nbsp;(make-label&nbsp;'compiled-branch))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(after-call&nbsp;(make-label&nbsp;'after-call)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((compiled-linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(eq?&nbsp;linkage&nbsp;'next)&nbsp;after-call&nbsp;linkage)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(proc)&nbsp;'()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(branch&nbsp;(label&nbsp;,primitive-branch))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(parallel-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;compiled-branch<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile-proc-appl&nbsp;target&nbsp;compiled-linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;primitive-branch<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(end-with-linkage&nbsp;linkage<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(proc&nbsp;argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;target)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;,target<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;apply-primitive-procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;argl)))))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;after-call))))<br>
</tt><p><p>
The primitive and compound branches, like the true
and false branches in <tt>compile-if</tt>, are appended using
<tt>parallel-instruction-sequences</tt> rather than the ordinary <tt>append-instruction-sequences</tt>, because they will
not be executed sequentially.<p>

<a name="%_sec_Temp_811"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_811">Applying compiled procedures</a></h4><p>

The code that handles procedure application is the most subtle part of
the compiler, even though the instruction sequences it generates are
very short.  A compiled procedure (as constructed by <tt>compile-lambda</tt>) has an entry point, which is a label that designates
where the code for the procedure starts.  The code at this entry point
computes a result in <tt>val</tt> and returns by executing the
instruction <tt>(goto (reg continue))</tt>.  Thus, we might expect the
code for a compiled-procedure application (to be generated by <tt>compile-proc-appl</tt>) with a given target and linkage to look like this
if the linkage is a label


<p><p><tt>&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;proc-return))<br>
&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
proc-return<br>
&nbsp;(assign&nbsp;&lt;<em>target</em>&gt;&nbsp;(reg&nbsp;val))&nbsp;&nbsp;&nbsp;<em>;&nbsp;included&nbsp;if&nbsp;target&nbsp;is&nbsp;not&nbsp;<tt>val</tt></em><br>
&nbsp;(goto&nbsp;(label&nbsp;&lt;<em>linkage</em>&gt;))&nbsp;&nbsp;&nbsp;<em>;&nbsp;linkage&nbsp;code</em><br>
</tt><p><p>
or like this if the linkage is <tt>return</tt>.

<p><p><tt>&nbsp;(save&nbsp;continue)<br>
&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;proc-return))<br>
&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
proc-return<br>
&nbsp;(assign&nbsp;&lt;<em>target</em>&gt;&nbsp;(reg&nbsp;val))&nbsp;&nbsp;&nbsp;<em>;&nbsp;included&nbsp;if&nbsp;target&nbsp;is&nbsp;not&nbsp;<tt>val</tt></em><br>
&nbsp;(restore&nbsp;continue)<br>
&nbsp;(goto&nbsp;(reg&nbsp;continue))&nbsp;&nbsp;&nbsp;<em>;&nbsp;linkage&nbsp;code</em><br>
</tt><p><p>
This code sets up <tt>continue</tt> so that the procedure will return to a
label <tt>proc-return</tt> and jumps to the procedure's entry point.  The code
at <tt>proc-return</tt> transfers the procedure's result from <tt>val</tt>
to the target register (if necessary) and then jumps to
the location specified by the linkage.
(The linkage is always <tt>return</tt> or a label, because <tt>compile-procedure-call</tt> replaces a <tt>next</tt> linkage for the
compound-procedure branch by an <tt>after-call</tt> label.)<p>


In fact, if the target is not <tt>val</tt>, that is exactly the code our
compiler will generate.<a name="call_footnote_Temp_812" href="#footnote_Temp_812"><sup><small>39</small></sup></a>
Usually, however, the target is <tt>val</tt> (the only time the compiler
specifies a different register is when targeting the evaluation of an
operator to <tt>proc</tt>), so the procedure result is put directly into
the target register and there is no need to return to a special
location that copies it.  Instead, we simplify the code by
setting up <tt>continue</tt> so that the procedure will ``return''
directly to the place specified by the caller's linkage:

<p><p><tt>&lt;<em>set&nbsp;up&nbsp;<tt>continue</tt>&nbsp;for&nbsp;linkage</em>&gt;<br>
(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
(goto&nbsp;(reg&nbsp;val))<br>
</tt><p><p>
If the linkage is a label, we set up <tt>continue</tt> so that the procedure will return to
that label.  (That is, the <tt>(goto (reg continue))</tt> the procedure
ends with becomes equivalent to the <tt>(goto (label &lt;<em>linkage</em>&gt;))</tt> at
<tt>proc-return</tt> above.)

<p><p><tt>(assign&nbsp;continue&nbsp;(label&nbsp;&lt;<em>linkage</em>&gt;))<br>
(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
(goto&nbsp;(reg&nbsp;val))<br>
</tt><p><p>
If the linkage is <tt>return</tt>, we don't need to set up <tt>continue</tt>
at all: It already holds the desired location.  (That is, the <tt>(goto (reg continue))</tt> the procedure ends with goes directly to the
place where the <tt>(goto (reg continue))</tt> at <tt>proc-return</tt> would
have gone.)

<p><p><tt>(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
(goto&nbsp;(reg&nbsp;val))<br>
</tt><p><p>
<a name="%_idx_6352"></a><a name="%_idx_6354"></a>With this implementation of the <tt>return</tt> linkage, the compiler
generates tail-recursive code.  Calling a procedure as the final step
in a procedure body does a direct transfer, without saving any
information on the stack.<p>


Suppose instead that we had handled the case of a procedure call with
a linkage of <tt>return</tt> and a target of <tt>val</tt> as shown above for
a non-<tt>val</tt> target.  This would destroy tail recursion.  Our
system would still give the same value for any expression.  But each
time we called a procedure, we would save <tt>continue</tt> and return
after the call to undo the (useless) save.  These extra saves would
accumulate during a nest of procedure calls.<a name="call_footnote_Temp_813" href="#footnote_Temp_813"><sup><small>40</small></sup></a><p>

<tt>Compile-proc-appl</tt> generates the above procedure-application code by
considering four cases, depending on whether the target for the call
is <tt>val</tt> and whether the linkage is <tt>return</tt>.
Observe that the instruction sequences are
declared to modify all the registers, since executing the procedure
body can change the registers in arbitrary ways.<a name="call_footnote_Temp_814" href="#footnote_Temp_814"><sup><small>41</small></sup></a>
Also note that the code sequence for the case with target <tt>val</tt>
and linkage <tt>return</tt> is declared to need <tt>continue</tt>:  Even
though <tt>continue</tt> is not explicitly used in the two-instruction
sequence, we must be sure that <tt>continue</tt> will have the correct
value when we enter the compiled procedure.<p>


<p><p><tt><a name="%_idx_6376"></a>(define&nbsp;(compile-proc-appl&nbsp;target&nbsp;linkage)<br>
&nbsp;&nbsp;(cond&nbsp;((and&nbsp;(eq?&nbsp;target&nbsp;'val)&nbsp;(not&nbsp;(eq?&nbsp;linkage&nbsp;'return)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(proc)&nbsp;all-regs<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;continue&nbsp;(label&nbsp;,linkage))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val)))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((and&nbsp;(not&nbsp;(eq?&nbsp;target&nbsp;'val))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(not&nbsp;(eq?&nbsp;linkage&nbsp;'return)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((proc-return&nbsp;(make-label&nbsp;'proc-return)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(proc)&nbsp;all-regs<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((assign&nbsp;continue&nbsp;(label&nbsp;,proc-return))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,proc-return<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assign&nbsp;,target&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goto&nbsp;(label&nbsp;,linkage))))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((and&nbsp;(eq?&nbsp;target&nbsp;'val)&nbsp;(eq?&nbsp;linkage&nbsp;'return))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence&nbsp;'(proc&nbsp;continue)&nbsp;all-regs<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'((assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val)))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((and&nbsp;(not&nbsp;(eq?&nbsp;target&nbsp;'val))&nbsp;(eq?&nbsp;linkage&nbsp;'return))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;&quot;return&nbsp;linkage,&nbsp;target&nbsp;not&nbsp;val&nbsp;--&nbsp;COMPILE&quot;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;target))))<br>
</tt><p><p>
<p>

<a name="%_sec_5.5.4"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.4">5.5.4&nbsp;&nbsp;Combining Instruction Sequences</a></h3><p>


<a name="%_idx_6378"></a>
This section describes the details on how instruction sequences are
represented and combined.  Recall from
section&nbsp;<a href="#%_sec_5.5.1">5.5.1</a> that an instruction sequence
is represented as a list of the registers needed, the registers
modified, and the actual instructions.  We will also consider a label
(symbol) to be a degenerate case of an instruction sequence, which doesn't
need or modify any registers.
So to determine the registers needed
and modified by instruction sequences we use the selectors
<p><p><tt><a name="%_idx_6380"></a>(define&nbsp;(registers-needed&nbsp;s)<br>
&nbsp;&nbsp;(if&nbsp;(symbol?&nbsp;s)&nbsp;'()&nbsp;(car&nbsp;s)))<br>
<a name="%_idx_6382"></a>(define&nbsp;(registers-modified&nbsp;s)<br>
&nbsp;&nbsp;(if&nbsp;(symbol?&nbsp;s)&nbsp;'()&nbsp;(cadr&nbsp;s)))<br>
<a name="%_idx_6384"></a>(define&nbsp;(statements&nbsp;s)<br>
&nbsp;&nbsp;(if&nbsp;(symbol?&nbsp;s)&nbsp;(list&nbsp;s)&nbsp;(caddr&nbsp;s)))<br>
</tt><p><p>
and to determine whether a given
sequence needs or modifies a given register we use the predicates
<p><p><tt><a name="%_idx_6386"></a>(define&nbsp;(needs-register?&nbsp;seq&nbsp;reg)<br>
&nbsp;&nbsp;(memq&nbsp;reg&nbsp;(registers-needed&nbsp;seq)))<br>
<a name="%_idx_6388"></a>(define&nbsp;(modifies-register?&nbsp;seq&nbsp;reg)<br>
&nbsp;&nbsp;(memq&nbsp;reg&nbsp;(registers-modified&nbsp;seq)))<br>
</tt><p><p>
In terms of these predicates and selectors, we can implement the
various instruction sequence combiners used throughout the compiler.<p>

The basic combiner is <tt>append-instruction-sequences</tt>.  This takes as
arguments an arbitrary number of instruction sequences that are to be executed
sequentially and returns an instruction sequence whose statements are the
statements of all the sequences appended together.  The subtle point is to
determine the registers that are needed and modified by the resulting
sequence.  It modifies those registers that are modified by any of the
sequences; it needs those registers that must be initialized before the first
sequence can be run (the registers needed by the first sequence), together
with those registers needed by any of the other sequences that are not
initialized (modified) by sequences preceding it.<p>

The sequences are appended two at a time by <tt>append-2-sequences</tt>.  This
takes two instruction sequences <tt>seq1</tt> and <tt>seq2</tt> and returns the
instruction sequence whose statements are the statements of <tt>seq1</tt>
followed by the statements of <tt>seq2</tt>, whose modified registers are those
registers that are modified by either <tt>seq1</tt> or <tt>seq2</tt>, and whose
needed registers are the registers needed by <tt>seq1</tt> together with those
registers needed by <tt>seq2</tt> that are not modified by <tt>seq1</tt>.  (In terms
of set operations, the new set of needed registers is the union of the set of
registers needed by <tt>seq1</tt> with the set difference of the registers needed
by <tt>seq2</tt> and the registers modified by <tt>seq1</tt>.)  Thus, <tt>append-instruction-sequences</tt> is implemented as follows:<p>

<p><p><tt><a name="%_idx_6390"></a>(define&nbsp;(append-instruction-sequences&nbsp;.&nbsp;seqs)<br>
&nbsp;&nbsp;(define&nbsp;(append-2-sequences&nbsp;seq1&nbsp;seq2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-union&nbsp;(registers-needed&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-difference&nbsp;(registers-needed&nbsp;seq2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(registers-modified&nbsp;seq1)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-union&nbsp;(registers-modified&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(registers-modified&nbsp;seq2))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append&nbsp;(statements&nbsp;seq1)&nbsp;(statements&nbsp;seq2))))<br>
&nbsp;&nbsp;(define&nbsp;(append-seq-list&nbsp;seqs)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(null?&nbsp;seqs)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(empty-instruction-sequence)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-2-sequences&nbsp;(car&nbsp;seqs)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-seq-list&nbsp;(cdr&nbsp;seqs)))))<br>
&nbsp;&nbsp;(append-seq-list&nbsp;seqs))<br>
</tt><p><p><p>

This procedure uses some simple operations for manipulating sets
represented as lists, similar to the (unordered) set representation
described in section&nbsp;<a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a>:
<p><p><tt><a name="%_idx_6392"></a>(define&nbsp;(list-union&nbsp;s1&nbsp;s2)<br>
&nbsp;&nbsp;(cond&nbsp;((null?&nbsp;s1)&nbsp;s2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((memq&nbsp;(car&nbsp;s1)&nbsp;s2)&nbsp;(list-union&nbsp;(cdr&nbsp;s1)&nbsp;s2))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(cons&nbsp;(car&nbsp;s1)&nbsp;(list-union&nbsp;(cdr&nbsp;s1)&nbsp;s2)))))<br>
<a name="%_idx_6394"></a>(define&nbsp;(list-difference&nbsp;s1&nbsp;s2)<br>
&nbsp;&nbsp;(cond&nbsp;((null?&nbsp;s1)&nbsp;'())<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((memq&nbsp;(car&nbsp;s1)&nbsp;s2)&nbsp;(list-difference&nbsp;(cdr&nbsp;s1)&nbsp;s2))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(cons&nbsp;(car&nbsp;s1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-difference&nbsp;(cdr&nbsp;s1)&nbsp;s2)))))<br>
</tt><p><p><p>


<tt>Preserving</tt>, the second major instruction sequence combiner, takes a list
of registers <tt>regs</tt> and two instruction sequences <tt>seq1</tt> and <tt>seq2</tt> that are to be executed sequentially.  It returns an instruction
sequence whose statements are the statements of <tt>seq1</tt> followed by the
statements of <tt>seq2</tt>, with appropriate <tt>save</tt> and <tt>restore</tt>
instructions around <tt>seq1</tt> to protect the registers in <tt>regs</tt> that are
modified by <tt>seq1</tt> but needed by <tt>seq2</tt>.  To accomplish this, <tt>preserving</tt> first creates a sequence that has the required <tt>save</tt>s
followed by the statements of <tt>seq1</tt> followed by the required <tt>restore</tt>s.  This sequence needs the registers being saved and restored in
addition to the registers needed by <tt>seq1</tt>, and modifies the registers
modified by <tt>seq1</tt> except for the ones being saved and restored.  This
augmented sequence and <tt>seq2</tt> are then appended in the usual way.  The
following procedure implements this strategy recursively, walking down the
list of registers to be preserved:<a name="call_footnote_Temp_815" href="#footnote_Temp_815"><sup><small>42</small></sup></a>
<p><p><tt><a name="%_idx_6398"></a>(define&nbsp;(preserving&nbsp;regs&nbsp;seq1&nbsp;seq2)<br>
&nbsp;&nbsp;(if&nbsp;(null?&nbsp;regs)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append-instruction-sequences&nbsp;seq1&nbsp;seq2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((first-reg&nbsp;(car&nbsp;regs)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(and&nbsp;(needs-register?&nbsp;seq2&nbsp;first-reg)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(modifies-register?&nbsp;seq1&nbsp;first-reg))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;(cdr&nbsp;regs)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-instruction-sequence<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-union&nbsp;(list&nbsp;first-reg)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(registers-needed&nbsp;seq1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list-difference&nbsp;(registers-modified&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;first-reg))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(append&nbsp;`((save&nbsp;,first-reg))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(statements&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`((restore&nbsp;,first-reg))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;seq2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(preserving&nbsp;(cdr&nbsp;regs)&nbsp;seq1&nbsp;seq2)))))<br>
</tt><p><p><p>

Another sequence combiner, <tt>tack-on-instruction-sequence</tt>,
is used by <tt>compile-lambda</tt> to append a procedure body to another
sequence.  Because the procedure body is not ``in line'' to be
executed as part of the combined sequence, its register use has no
impact on the register use of the sequence in which it is embedded.
We thus ignore the procedure body's sets of needed and modified
registers when we tack it onto the other sequence.<p>

<p><p><tt><a name="%_idx_6400"></a>(define&nbsp;(tack-on-instruction-sequence&nbsp;seq&nbsp;body-seq)<br>
&nbsp;&nbsp;(make-instruction-sequence<br>
&nbsp;&nbsp;&nbsp;(registers-needed&nbsp;seq)<br>
&nbsp;&nbsp;&nbsp;(registers-modified&nbsp;seq)<br>
&nbsp;&nbsp;&nbsp;(append&nbsp;(statements&nbsp;seq)&nbsp;(statements&nbsp;body-seq))))<br>
</tt><p><p><p>

<tt>Compile-if</tt> and <tt>compile-procedure-call</tt> use a special
combiner called <tt>parallel-instruction-sequences</tt> to append the two
alternative branches that follow a test.  The two branches will never be
executed sequentially; for any particular evaluation of the test, one
branch or the other will be entered.  Because of this, the registers
needed by the second branch are still needed by the combined sequence,
even if these are modified by the first branch.<p>

<p><p><tt><a name="%_idx_6402"></a>(define&nbsp;(parallel-instruction-sequences&nbsp;seq1&nbsp;seq2)<br>
&nbsp;&nbsp;(make-instruction-sequence<br>
&nbsp;&nbsp;&nbsp;(list-union&nbsp;(registers-needed&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(registers-needed&nbsp;seq2))<br>
&nbsp;&nbsp;&nbsp;(list-union&nbsp;(registers-modified&nbsp;seq1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(registers-modified&nbsp;seq2))<br>
&nbsp;&nbsp;&nbsp;(append&nbsp;(statements&nbsp;seq1)&nbsp;(statements&nbsp;seq2))))<br>
</tt><p><p><p>

<a name="%_sec_5.5.5"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.5">5.5.5&nbsp;&nbsp;An Example of Compiled Code</a></h3><p>

<a name="%_idx_6404"></a><a name="%_idx_6406"></a>
Now that we have seen all the elements of the compiler, let us examine
an example of compiled code to see how things fit together.  We will
compile the definition of a recursive <tt>factorial</tt> procedure by
calling <tt>compile</tt>:<p>

<p><p><tt>(compile<br>
&nbsp;'(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n)))<br>
&nbsp;'val<br>
&nbsp;'next)<br>
</tt><p><p>
We have specified that the value of the <tt>define</tt> expression should
be placed in the <tt>val</tt> register.  We don't care what the compiled
code does after executing the <tt>define</tt>, so our choice of <tt>next</tt> as the linkage descriptor is arbitrary.<p>

<tt>Compile</tt> determines that the expression is a definition, so it calls <tt>compile-definition</tt> to compile code to compute the value to be assigned
(targeted to <tt>val</tt>), followed by code to install the definition, followed
by code to put the value of the <tt>define</tt> (which is the symbol <tt>ok</tt>)
into the target register, followed finally by the linkage code.  <tt>Env</tt> is
preserved around the computation of the value, because it is needed in order
to install the definition.  Because the linkage is <tt>next</tt>, there is no
linkage code in this case.  The skeleton of the compiled code is thus<p>

<p><p><tt>&nbsp;&nbsp;&lt;<em>save&nbsp;<tt>env</tt>&nbsp;if&nbsp;modified&nbsp;by&nbsp;code&nbsp;to&nbsp;compute&nbsp;value</em>&gt;<br>
&nbsp;&nbsp;&lt;<em>compilation&nbsp;of&nbsp;definition&nbsp;value,&nbsp;target&nbsp;<tt>val</tt>,&nbsp;linkage&nbsp;<tt>next</tt></em>&gt;<br>
&nbsp;&nbsp;&lt;<em>restore&nbsp;<tt>env</tt>&nbsp;if&nbsp;saved&nbsp;above</em>&gt;<br>
&nbsp;&nbsp;(perform&nbsp;(op&nbsp;define-variable!)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;factorial)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;val)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;ok))<br>
</tt><p><p><p>

The expression that is to be compiled to produce the value for the
variable <tt>factorial</tt> is a <tt>lambda</tt> expression whose value is
the procedure that computes factorials.  <tt>Compile</tt> handles this by
calling <tt>compile-lambda</tt>, which compiles the procedure body,
labels it as a new entry point, and generates the instruction that
will combine the procedure body at the new entry point with the
run-time environment and assign the result to <tt>val</tt>.  The sequence
then skips around the compiled procedure code, which is inserted at
this point.  The procedure code itself begins by extending the
procedure's definition environment by a frame that binds
the formal parameter <tt>n</tt> to the procedure argument.  Then comes the actual
procedure body.  Since this code for the value of the variable
doesn't modify the <tt>env</tt> register, the optional <tt>save</tt>
and <tt>restore</tt> shown above aren't generated.  (The procedure code at
<tt>entry2</tt> isn't executed at this point, so its use of <tt>env</tt>
is irrelevant.)
Therefore, the skeleton for the compiled code becomes<p>

<p><p><tt>&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;make-compiled-procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(label&nbsp;entry2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(goto&nbsp;(label&nbsp;after-lambda1))<br>
entry2<br>
&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;compiled-procedure-env)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;extend-environment)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;(n))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;argl)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;&lt;<em>compilation&nbsp;of&nbsp;procedure&nbsp;body</em>&gt;<br>
after-lambda1<br>
&nbsp;&nbsp;(perform&nbsp;(op&nbsp;define-variable!)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(const&nbsp;factorial)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;val)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;ok))<br>
</tt><p><p><p>

A procedure body is always compiled (by <tt>compile-lambda-body</tt>) as
a sequence with target <tt>val</tt> and linkage <tt>return</tt>.  The
sequence in this case consists of a single <tt>if</tt> expression:<p>

<p><p><tt>(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n))<br>
</tt><p><p>
<tt>Compile-if</tt> generates code that first computes the predicate (targeted to
<tt>val</tt>), then checks the result and branches around the true branch if the
predicate is false.  <tt>Env</tt> and <tt>continue</tt> are preserved around the
predicate code, since they may be needed for the rest of the <tt>if</tt>
expression.  Since the <tt>if</tt> expression is the final expression (and only
expression) in the sequence making up the procedure body, its target is <tt>val</tt> and its linkage is <tt>return</tt>, so the true and false branches are both
compiled with target <tt>val</tt> and linkage <tt>return</tt>.
(That is, the value of the conditional, which is the value computed by
either of its branches, is the value of the procedure.)<p>

<p><p><tt>&nbsp;&nbsp;&lt;<em>save&nbsp;<tt>continue</tt>,&nbsp;<tt>env</tt>&nbsp;if&nbsp;modified&nbsp;by&nbsp;predicate&nbsp;and&nbsp;needed&nbsp;by&nbsp;branches</em>&gt;<br>
&nbsp;&nbsp;&lt;<em>compilation&nbsp;of&nbsp;predicate,&nbsp;target&nbsp;<tt>val</tt>,&nbsp;linkage&nbsp;<tt>next</tt></em>&gt;<br>
&nbsp;&nbsp;&lt;<em>restore&nbsp;<tt>continue</tt>,&nbsp;<tt>env</tt>&nbsp;if&nbsp;saved&nbsp;above</em>&gt;<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;false?)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;false-branch4))<br>
true-branch5<br>
&nbsp;&nbsp;&lt;<em>compilation&nbsp;of&nbsp;true&nbsp;branch,&nbsp;target&nbsp;<tt>val</tt>,&nbsp;linkage&nbsp;<tt>return</tt></em>&gt;<br>
false-branch4<br>
&nbsp;&nbsp;&lt;<em>compilation&nbsp;of&nbsp;false&nbsp;branch,&nbsp;target&nbsp;<tt>val</tt>,&nbsp;linkage&nbsp;<tt>return</tt></em>&gt;<br>
after-if3<br>
</tt><p><p><p>

The predicate <tt>(= n 1)</tt> is a procedure call.  This
looks up the operator (the symbol <tt>=</tt>) and places this value in
<tt>proc</tt>.  It then assembles the arguments <tt>1</tt> and the value of
<tt>n</tt> into <tt>argl</tt>.  Then it tests whether <tt>proc</tt> contains a
primitive or a compound procedure, and dispatches to a primitive branch
or a compound branch accordingly.  Both branches resume at the <tt>after-call</tt> label.  The requirements to preserve registers
around the evaluation of the operator and operands don't result in
any saving of registers, because in this case those evaluations don't
modify the registers in question.<p>

<p><p><tt>&nbsp;&nbsp;(assign&nbsp;proc<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;=)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;1))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;n)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch17))<br>
compiled-branch16<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call15))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch17<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;proc)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;argl))<br>
after-call15<br>
</tt><p><p><p>

The true branch, which is the constant 1, compiles (with target
<tt>val</tt> and linkage <tt>return</tt>) to<p>

<p><p><tt>&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;1))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;continue))<br>
</tt><p><p>
The code for the false branch is another a procedure call, where the
procedure is the value of the symbol <tt>*</tt>, and the arguments are
<tt>n</tt> and the result of another procedure call (a call to <tt>factorial</tt>).
Each of these calls sets up <tt>proc</tt> and <tt>argl</tt> and its own primitive
and compound branches.  Figure&nbsp;<a href="#%_fig_5.17">5.17</a>
shows the complete compilation of the
definition of the <tt>factorial</tt> procedure.
Notice that the possible <tt>save</tt> and <tt>restore</tt> of
<tt>continue</tt> and <tt>env</tt> around the predicate, shown above,
are in fact generated, because these registers are modified by the procedure
call in the predicate and needed for the procedure call and the
<tt>return</tt> linkage in the branches.


<p><a name="%_thm_5.33"></a>
<b>Exercise 5.33.</b>&nbsp;&nbsp;Consider the following definition of a factorial procedure, which is
slightly different from the one given above:
<p><p><tt>(define&nbsp;(factorial-alt&nbsp;n)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;n&nbsp;(factorial-alt&nbsp;(-&nbsp;n&nbsp;1)))))<br>
</tt><p><p>
Compile this procedure and compare the resulting code with that produced for
<tt>factorial</tt>.  Explain any differences you find.  Does either
program execute more efficiently than the other?
<p><p>

<p><a name="%_thm_5.34"></a>
<b>Exercise 5.34.</b>&nbsp;&nbsp;<a name="%_idx_6408"></a><a name="%_idx_6410"></a>Compile the iterative factorial procedure
<p><p><tt>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;product&nbsp;counter)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;counter&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(*&nbsp;counter&nbsp;product)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;counter&nbsp;1))))<br>
&nbsp;&nbsp;(iter&nbsp;1&nbsp;1))<br>
</tt><p><p>
Annotate the resulting code, showing the essential difference between
the code for iterative and recursive versions of <tt>factorial</tt> that
makes one process build up stack space and the other run in constant
stack space.
<p>


<p>

<a name="%_fig_5.17"></a><p><div align=left><table width=100%><tr><td><p><p><tt><em>;;&nbsp;construct&nbsp;the&nbsp;procedure&nbsp;and&nbsp;skip&nbsp;over&nbsp;code&nbsp;for&nbsp;the&nbsp;procedure&nbsp;body</em><br>
&nbsp;&nbsp;(assign&nbsp;val<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;make-compiled-procedure)&nbsp;(label&nbsp;entry2)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(goto&nbsp;(label&nbsp;after-lambda1))<br>
<br>
entry2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;calls&nbsp;to&nbsp;<tt>factorial</tt>&nbsp;will&nbsp;enter&nbsp;here</em><br>
&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;compiled-procedure-env)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(assign&nbsp;env<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;extend-environment)&nbsp;(const&nbsp;(n))&nbsp;(reg&nbsp;argl)&nbsp;(reg&nbsp;env))<br>
<em>;;&nbsp;begin&nbsp;actual&nbsp;procedure&nbsp;body</em><br>
&nbsp;&nbsp;(save&nbsp;continue)<br>
&nbsp;&nbsp;(save&nbsp;env)<br>
<br>
<em>;;&nbsp;compute&nbsp;<tt>(=&nbsp;n&nbsp;1)</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;=)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;1))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;n)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch17))<br>
compiled-branch16<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call15))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch17<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
<br>
after-call15&nbsp;&nbsp;&nbsp;<em>;&nbsp;<tt>val</tt>&nbsp;now&nbsp;contains&nbsp;result&nbsp;of&nbsp;<tt>(=&nbsp;n&nbsp;1)</tt></em><br>
&nbsp;&nbsp;(restore&nbsp;env)<br>
&nbsp;&nbsp;(restore&nbsp;continue)<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;false?)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;false-branch4))<br>
true-branch5&nbsp;&nbsp;<em>;&nbsp;return&nbsp;1</em><br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;1))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;continue))<br>
<br>
false-branch4<br>
<em>;;&nbsp;compute&nbsp;and&nbsp;return&nbsp;<tt>(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n)</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;*)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(save&nbsp;continue)<br>
&nbsp;&nbsp;(save&nbsp;proc)&nbsp;&nbsp;&nbsp;<em>;&nbsp;save&nbsp;<tt>*</tt></em>&nbsp;procedure<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;n)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(save&nbsp;argl)&nbsp;&nbsp;&nbsp;<em>;&nbsp;save&nbsp;partial&nbsp;argument&nbsp;list&nbsp;for&nbsp;<tt>*</tt></em><br>
<br>
<em>;;&nbsp;compute&nbsp;<tt>(factorial&nbsp;(-&nbsp;n&nbsp;1))</tt>,&nbsp;which&nbsp;is&nbsp;the&nbsp;other&nbsp;argument&nbsp;for&nbsp;<tt>*</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;proc<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;factorial)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(save&nbsp;proc)&nbsp;&nbsp;<em>;&nbsp;save&nbsp;<tt>factorial</tt>&nbsp;procedure</em><br>
</tt><p><p>
<p><p></td></tr><caption align=bottom><div align=left><b>Figure 5.17:</b>&nbsp;&nbsp;Compilation of the definition of the <tt>factorial</tt>
procedure (continued on next page).</div></caption><tr><td>
<a name="%_idx_6412"></a>

</td></tr></table></div><p><p>

<a name="%_fig_5.17"></a><p><div align=left><table width=100%><tr><td><p><p><tt><em>;;&nbsp;compute&nbsp;<tt>(-&nbsp;n&nbsp;1)</tt>,&nbsp;which&nbsp;is&nbsp;the&nbsp;argument&nbsp;for&nbsp;<tt>factorial</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;-)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;1))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;n)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch8))<br>
compiled-branch7<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call6))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch8<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
<br>
after-call6&nbsp;&nbsp;&nbsp;<em>;&nbsp;<tt>val</tt>&nbsp;now&nbsp;contains&nbsp;result&nbsp;of&nbsp;<tt>(-&nbsp;n&nbsp;1)</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(restore&nbsp;proc)&nbsp;<em>;&nbsp;restore&nbsp;<tt>factorial</tt></em><br>
<em>;;&nbsp;apply&nbsp;<tt>factorial</tt></em><br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch11))<br>
compiled-branch10<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call9))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch11<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
<br>
after-call9&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;<tt>val</tt>&nbsp;now&nbsp;contains&nbsp;result&nbsp;of&nbsp;<tt>(factorial&nbsp;(-&nbsp;n&nbsp;1))</tt></em><br>
&nbsp;&nbsp;(restore&nbsp;argl)&nbsp;<em>;&nbsp;restore&nbsp;partial&nbsp;argument&nbsp;list&nbsp;for&nbsp;<tt>*</tt></em><br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(restore&nbsp;proc)&nbsp;<em>;&nbsp;restore&nbsp;<tt>*</tt></em><br>
&nbsp;&nbsp;(restore&nbsp;continue)<br>
<em>;;&nbsp;apply&nbsp;<tt>*</tt></em>&nbsp;and&nbsp;return&nbsp;its&nbsp;value<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch14))<br>
compiled-branch13<br>
<em>;;&nbsp;note&nbsp;that&nbsp;a&nbsp;compound&nbsp;procedure&nbsp;here&nbsp;is&nbsp;called&nbsp;tail-recursively</em><br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch14<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;continue))<br>
after-call12<br>
after-if3<br>
after-lambda1<br>
<em>;;&nbsp;assign&nbsp;the&nbsp;procedure&nbsp;to&nbsp;the&nbsp;variable&nbsp;<tt>factorial</tt></em><br>
&nbsp;&nbsp;(perform<br>
&nbsp;&nbsp;&nbsp;(op&nbsp;define-variable!)&nbsp;(const&nbsp;factorial)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;ok))<br>
</tt><p><p>
<p><p></td></tr><caption align=bottom><div align=left><b>Figure 5.17:</b>&nbsp;&nbsp;(continued)</div></caption><tr><td>
</td></tr></table></div><p><p>

<p><a name="%_thm_5.35"></a>
<b>Exercise 5.35.</b>&nbsp;&nbsp;What expression was compiled to produce the code shown in
figure&nbsp;<a href="#%_fig_5.18">5.18</a>?
<a name="%_fig_5.18"></a><p><div align=left><table width=100%><tr><td><p><p><tt>&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;make-compiled-procedure)&nbsp;(label&nbsp;entry16)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(goto&nbsp;(label&nbsp;after-lambda15))<br>
entry16<br>
&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;compiled-procedure-env)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(assign&nbsp;env<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(op&nbsp;extend-environment)&nbsp;(const&nbsp;(x))&nbsp;(reg&nbsp;argl)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;+)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(save&nbsp;continue)<br>
&nbsp;&nbsp;(save&nbsp;proc)<br>
&nbsp;&nbsp;(save&nbsp;env)<br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;g)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(save&nbsp;proc)<br>
&nbsp;&nbsp;(assign&nbsp;proc&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;+)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;2))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;x)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch19))<br>
compiled-branch18<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call17))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch19<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
after-call17<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(restore&nbsp;proc)<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch22))<br>
compiled-branch21<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;after-call20))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch22<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
</tt><p><p>
<p><p></td></tr><caption align=bottom><div align=left><b>Figure 5.18:</b>&nbsp;&nbsp;An example of compiler output (continued on next page).
See exercise&nbsp;<a href="#%_thm_5.35">5.35</a>.</div></caption><tr><td>


</td></tr></table></div><p><p>

<a name="%_fig_5.18"></a><p><div align=left><table width=100%><tr><td><p><p><tt>after-call20<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;list)&nbsp;(reg&nbsp;val))<br>
&nbsp;&nbsp;(restore&nbsp;env)<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;x)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;argl&nbsp;(op&nbsp;cons)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(restore&nbsp;proc)<br>
&nbsp;&nbsp;(restore&nbsp;continue)<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-branch25))<br>
compiled-branch24<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
primitive-branch25<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;apply-primitive-procedure)&nbsp;(reg&nbsp;proc)&nbsp;(reg&nbsp;argl))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;continue))<br>
after-call23<br>
after-lambda15<br>
&nbsp;&nbsp;(perform&nbsp;(op&nbsp;define-variable!)&nbsp;(const&nbsp;f)&nbsp;(reg&nbsp;val)&nbsp;(reg&nbsp;env))<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(const&nbsp;ok))<br>
</tt><p><p>
<p><p></td></tr><caption align=bottom><div align=left><b>Figure 5.18:</b>&nbsp;&nbsp;(continued)</div></caption><tr><td>
</td></tr></table></div><p>
<p><p>

<p><a name="%_thm_5.36"></a>
<b>Exercise 5.36.</b>&nbsp;&nbsp;<a name="%_idx_6414"></a><a name="%_idx_6416"></a>What order of evaluation does our compiler produce for operands of a
combination?  Is it left-to-right, right-to-left, or some other order?
Where in the compiler is this order determined?  Modify the compiler
so that it produces some other order of evaluation.  (See the
discussion of order of evaluation for the explicit-control evaluator
in section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>.)  How does changing the order of
operand evaluation affect the efficiency of the code that constructs
the argument list?
<p><p>

<p><a name="%_thm_5.37"></a>
<b>Exercise 5.37.</b>&nbsp;&nbsp;<a name="%_idx_6418"></a><a name="%_idx_6420"></a>One way to understand the compiler's <tt>preserving</tt> mechanism for
optimizing stack usage is to see what extra operations would
be generated if we did not use this idea.  Modify <tt>preserving</tt> so
that it always generates the <tt>save</tt> and <tt>restore</tt> operations.
Compile some simple expressions and identify the unnecessary stack
operations that are generated.
Compare the code to that generated with the <tt>preserving</tt> mechanism intact.
<p><p>

<p><a name="%_thm_5.38"></a>
<b>Exercise 5.38.</b>&nbsp;&nbsp;<a name="%_idx_6422"></a><a name="%_idx_6424"></a>Our compiler is clever about avoiding unnecessary stack operations,
but it is not clever at all when it comes to compiling calls to the primitive
procedures of the language in terms of the primitive operations
supplied by the machine.  For example, consider how much code is
compiled to compute <tt>(+ a 1)</tt>: The code sets up an argument list
in <tt>argl</tt>, puts the primitive addition procedure (which it finds
by looking up the symbol <tt>+</tt> in the environment) into <tt>proc</tt>,
and tests whether the procedure is primitive or compound.  The
compiler always generates code to perform the test, as well as code
for primitive and compound branches (only one of which will be executed).
We have not shown the part of the controller that implements
primitives, but we presume that these instructions make use of
primitive arithmetic operations in the machine's data paths.  Consider
how much less code would be generated if the compiler could <em>open-code</em> primitives -- that is, if it could generate code to directly
use these primitive machine operations.  The expression <tt>(+ a 1)</tt>
might be compiled into something as simple as&nbsp;<a name="call_footnote_Temp_822" href="#footnote_Temp_822"><sup><small>43</small></sup></a>
<p><p><tt>(assign&nbsp;val&nbsp;(op&nbsp;lookup-variable-value)&nbsp;(const&nbsp;a)&nbsp;(reg&nbsp;env))<br>
(assign&nbsp;val&nbsp;(op&nbsp;+)&nbsp;(reg&nbsp;val)&nbsp;(const&nbsp;1))<br>
</tt><p><p>
In this exercise we will extend our compiler to support open coding of
selected primitives.  Special-purpose code will be generated
for calls to these primitive procedures instead of the general
procedure-application code.  In order to support this, we will augment
our machine with special argument registers <tt>arg1</tt> and <tt>arg2</tt>.
The primitive arithmetic operations of the machine will take their
inputs from <tt>arg1</tt> and <tt>arg2</tt>. The results may be put into
<tt>val</tt>, <tt>arg1</tt>, or <tt>arg2</tt>.<p>

The compiler must be able to recognize the application of an
open-coded primitive in the source program.  We will augment the
dispatch in the <tt>compile</tt> procedure to recognize the names of
these primitives in addition to the <a name="%_idx_6426"></a>reserved words (the special forms)
it currently recognizes.<a name="call_footnote_Temp_823" href="#footnote_Temp_823"><sup><small>44</small></sup></a> For each special form our compiler has a code generator.  In
this exercise we will construct a family of code generators for the
open-coded primitives.<p>


a.&nbsp;&nbsp;The open-coded primitives, unlike the special forms, all need their
operands evaluated.  Write a code generator <tt>spread-arguments</tt> for use by
all the open-coding code generators.  <tt>Spread-arguments</tt> should take an
operand list and compile the given operands targeted to successive argument
registers.  Note that an operand may contain a call to an open-coded
primitive, so argument registers will have to be preserved during operand
evaluation.<p>

b.&nbsp;&nbsp;For each of the primitive procedures <tt>=</tt>, <tt>*</tt>, <tt>-</tt>, and
<tt>+</tt>, write a code generator that takes a combination with that
operator, together with a target and a linkage descriptor, and
produces code to spread the arguments into the registers and then
perform the operation targeted to the given target with the given
linkage.  You need only handle expressions with two operands.  Make
<tt>compile</tt> dispatch to these code generators.<p>

c.&nbsp;&nbsp;Try your new compiler on the <tt>factorial</tt> example.  Compare the
resulting code with the result produced without open coding.<p>

d.&nbsp;&nbsp;Extend your code generators for <tt>+</tt> and <tt>*</tt> so that they
can handle expressions with arbitrary numbers of operands.  An
expression with more than two operands will have to be compiled into a
sequence of operations, each with only two inputs.

<p><p>

<a name="%_sec_5.5.6"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.6">5.5.6&nbsp;&nbsp;Lexical Addressing</a></h3><p>


<a name="%_idx_6428"></a><a name="%_idx_6430"></a>

One of the most common optimizations performed by compilers is the
optimization of variable lookup.  Our compiler, as we have implemented
it so far, generates code that uses the <tt>lookup-variable-value</tt>
operation of the evaluator machine.  This searches for a variable by
comparing it with each variable that is currently bound, working frame
by frame outward through the run-time environment.  This search can be
expensive if the frames are deeply nested or if there are many
variables.  For example, consider the problem of looking up the value
of <tt>x</tt> while evaluating the expression <tt>(* x y z)</tt> in an
application of the procedure that is returned by<p>

<p><p><tt>(let&nbsp;((x&nbsp;3)&nbsp;(y&nbsp;4))<br>
&nbsp;&nbsp;(lambda&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((y&nbsp;(*&nbsp;a&nbsp;b&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(z&nbsp;(+&nbsp;c&nbsp;d&nbsp;x)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;x&nbsp;y&nbsp;z))))<br>
</tt><p><p>
Since a <tt>let</tt> expression is just syntactic sugar for a <tt>lambda</tt> combination, this expression is equivalent to<p>

<p><p><tt>((lambda&nbsp;(x&nbsp;y)<br>
&nbsp;&nbsp;&nbsp;(lambda&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((lambda&nbsp;(y&nbsp;z)&nbsp;(*&nbsp;x&nbsp;y&nbsp;z))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;a&nbsp;b&nbsp;x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;c&nbsp;d&nbsp;x))))<br>
&nbsp;3<br>
&nbsp;4)<br>
</tt><p><p>
Each time <tt>lookup-variable-value</tt> searches for <tt>x</tt>, it must
determine that the symbol <tt>x</tt> is not <tt>eq?</tt> to <tt>y</tt> or <tt>z</tt> (in the first frame), nor to <tt>a</tt>, <tt>b</tt>, <tt>c</tt>, <tt>d</tt>, or
<tt>e</tt> (in the second frame).  We will assume, for the moment, that
our programs do not use <tt>define</tt> -- that variables are
bound only with <tt>lambda</tt>.  Because our language is <a name="%_idx_6432"></a>lexically
scoped, the run-time environment for any expression will have a
structure that parallels the lexical structure of the program in which
the expression appears.<a name="call_footnote_Temp_824" href="#footnote_Temp_824"><sup><small>45</small></sup></a>
Thus, the compiler can know, when it analyzes the
above expression, that each time the procedure is applied the variable
<tt>x</tt> in <tt>(* x y z)</tt> will be found two frames out from the
current frame and will be the first variable in that frame.<p>

<a name="%_idx_6434"></a>We can exploit this fact by inventing a new kind of variable-lookup
operation, <tt>lexical-address-lookup</tt>, that takes as arguments an
environment and a <em>lexical address</em> that consists of two numbers:
a <em>frame number</em>, which specifies how many frames to pass over,
and a <em>displacement number</em>, which specifies how many variables to
pass over in that frame.  <a name="%_idx_6436"></a><tt>Lexical-address-lookup</tt> will produce
the value of the variable stored at that lexical address relative to
the current environment.  If we add the <tt>lexical-address-lookup</tt>
operation to our machine, we can make the compiler generate code that
references variables using this operation, rather than <tt>lookup-variable-value</tt>.  Similarly, our compiled code can use a new
<a name="%_idx_6438"></a><tt>lexical-address-set!</tt>  operation instead of <tt>set-variable-value!</tt>.<p>

In order to generate such code, the compiler must be able to determine
the lexical address of a variable it is about to compile a reference
to.  The lexical address of a variable in a program depends on where
one is in the code.  For example, in the following program, the
address of <tt>x</tt> in expression &lt;<em>e1</em>&gt; is (2,0) -- two frames back
and the first variable in the frame.  At that point <tt>y</tt> is at
address (0,0) and <tt>c</tt> is at address (1,2).  In expression
&lt;<em>e2</em>&gt;,  <tt>x</tt> is at (1,0),   <tt>y</tt> is at (1,1), and <tt>c</tt> is at (0,2).<p>

<p><p><tt>((lambda&nbsp;(x&nbsp;y)<br>
&nbsp;&nbsp;&nbsp;(lambda&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((lambda&nbsp;(y&nbsp;z)&nbsp;&lt;<em>e1</em>&gt;)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>e2</em>&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;c&nbsp;d&nbsp;x))))<br>
&nbsp;3<br>
&nbsp;4)<br>
</tt><p><p><p>

<a name="%_idx_6440"></a>One way for the compiler to produce code that uses lexical addressing
is to maintain a data structure called a <em>compile-time
environment</em>.  This keeps track of which variables will be at which
positions in which frames in the run-time environment when a
particular variable-access operation is executed.  The compile-time
environment is a list of frames, each containing a list of variables.
(There will of course be no values bound to the variables, since
values are not computed at compile time.)  The compile-time
environment becomes an additional argument to <tt>compile</tt> and is
passed along to each code generator.  The top-level call to <tt>compile</tt> uses an empty compile-time environment.
When a <tt>lambda</tt> body is compiled, <tt>compile-lambda-body</tt>
extends the compile-time environment by a frame containing the
procedure's parameters, so that the sequence making up the body
is compiled with that extended environment.
At each point in the compilation, <tt>compile-variable</tt> and <tt>compile-assignment</tt> use the compile-time
environment in order to generate the appropriate lexical addresses.<p>

Exercises&nbsp;<a href="#%_thm_5.39">5.39</a>
through&nbsp;<a href="#%_thm_5.43">5.43</a> describe how to complete this sketch of
the lexical-addressing strategy in order to incorporate lexical lookup
into the compiler.
Exercise&nbsp;<a href="#%_thm_5.44">5.44</a> describes another use for the
compile-time environment.<p>

<p><a name="%_thm_5.39"></a>
<b>Exercise 5.39.</b>&nbsp;&nbsp;<a name="%_idx_6442"></a><a name="%_idx_6444"></a>Write a procedure <tt>lexical-address-lookup</tt> that implements the new
lookup operation.  It should take two arguments -- a lexical address
and a run-time environment -- and return the value of the variable
stored at the specified lexical address.  <tt>Lexical-address-lookup</tt>
should signal an error if the value of the variable is the symbol <tt>*unassigned*</tt>.<a name="call_footnote_Temp_826" href="#footnote_Temp_826"><sup><small>46</small></sup></a> Also write a procedure <tt>lexical-address-set!</tt> that
implements the operation that changes the value of the variable at a
specified lexical address.


<p><p>

<p><a name="%_thm_5.40"></a>
<b>Exercise 5.40.</b>&nbsp;&nbsp;<a name="%_idx_6450"></a>Modify the compiler to maintain the compile-time environment as
described above.  That is, add a compile-time-environment argument to
<tt>compile</tt> and the various code generators, and extend it in
<tt>compile-lambda-body</tt>.
<p><p>

<p><a name="%_thm_5.41"></a>
<b>Exercise 5.41.</b>&nbsp;&nbsp;<a name="%_idx_6452"></a>Write a procedure <tt>find-variable</tt> that takes as arguments a
variable and a compile-time environment and returns the lexical
address of the variable with respect to that environment.  For
example, in the program fragment that is shown above, the compile-time
environment during the compilation of expression &lt;<em>e1</em>&gt; is <tt>((y
z) (a b c d e) (x y))</tt>.  <tt>Find-variable</tt> should produce<p>

<p><p><tt>(find-variable&nbsp;'c&nbsp;'((y&nbsp;z)&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)&nbsp;(x&nbsp;y)))<br>
<i>(1&nbsp;2)</i><br>
<br>
(find-variable&nbsp;'x&nbsp;'((y&nbsp;z)&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)&nbsp;(x&nbsp;y)))<br>
<i>(2&nbsp;0)</i><br>
<br>
(find-variable&nbsp;'w&nbsp;'((y&nbsp;z)&nbsp;(a&nbsp;b&nbsp;c&nbsp;d&nbsp;e)&nbsp;(x&nbsp;y)))<br>
<i>not-found</i><br>
</tt><p><p>
<p><p>

<p><a name="%_thm_5.42"></a>
<b>Exercise 5.42.</b>&nbsp;&nbsp;Using <tt>find-variable</tt> from exercise&nbsp;<a href="#%_thm_5.41">5.41</a>,
rewrite <tt>compile-variable</tt> and <tt>compile-assignment</tt> to output
lexical-address instructions.  In cases where <tt>find-variable</tt>
returns <tt>not-found</tt> (that is, where the variable is not in the
compile-time environment), you should have the code generators use the
evaluator operations, as before, to search for the binding.
(The only place a variable that is not found at compile time can be is in
the global environment, which is part of the run-time environment but
is not part of the compile-time environment.<a name="call_footnote_Temp_830" href="#footnote_Temp_830"><sup><small>47</small></sup></a>
Thus, if you wish, you may have the evaluator operations look directly in
the global environment, which can be obtained with the operation <tt>(op&nbsp;get-global-environment)</tt>, instead of having them search the whole run-time
environment found in <tt>env</tt>.)
Test the modified compiler on a few simple cases, such as the nested
<tt>lambda</tt> combination at the beginning of this section.

<p><p>

<p><a name="%_thm_5.43"></a>
<b>Exercise 5.43.</b>&nbsp;&nbsp;<a name="%_idx_6454"></a><a name="%_idx_6456"></a>We argued in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a> that internal definitions
for block structure should not be considered ``real'' <tt>define</tt>s.  Rather,
a procedure body should be interpreted as if the internal variables being
defined were installed as ordinary <tt>lambda</tt> variables initialized to their
correct values using <tt>set!</tt>.  Section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a> and
exercise&nbsp;<a href="book-Z-H-26.html#%_thm_4.16">4.16</a> showed how to modify the metacircular
interpreter to accomplish this by scanning out internal definitions.  Modify
the compiler to perform the same transformation before it compiles a procedure
body.


<p><p>

<p><a name="%_thm_5.44"></a>
<b>Exercise 5.44.</b>&nbsp;&nbsp;<a name="%_idx_6458"></a><a name="%_idx_6460"></a><a name="%_idx_6462"></a><a name="%_idx_6464"></a>In this section we have focused on the use of the compile-time
environment to produce lexical addresses.  But there are other uses
for compile-time environments.  For instance, in
exercise&nbsp;<a href="#%_thm_5.38">5.38</a> we increased the efficiency of compiled
code by open-coding primitive procedures.  Our implementation treated
the names of open-coded procedures as reserved words.  If a program
were to rebind such a name, the mechanism described in
exercise&nbsp;<a href="#%_thm_5.38">5.38</a> would still open-code it as a primitive,
ignoring the new binding.  For example, consider the procedure<p>

<p><p><tt>(lambda&nbsp;(+&nbsp;*&nbsp;a&nbsp;b&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(+&nbsp;(*&nbsp;a&nbsp;x)&nbsp;(*&nbsp;b&nbsp;y)))<br>
</tt><p><p>
which computes a linear combination of <tt>x</tt> and <tt>y</tt>.  We might
call it with arguments <tt>+matrix</tt>, <tt>*matrix</tt>, and four
matrices, but the open-coding compiler would still open-code the <tt>+</tt> and the <tt>*</tt> in <tt>(+ (* a x) (* b y))</tt> as primitive <tt>+</tt>
and <tt>*</tt>.  Modify the open-coding compiler to consult the
compile-time environment in order to compile the correct code for
expressions involving the names of primitive procedures.
(The code will work correctly as long as the program does not <tt>define</tt> or <tt>set!</tt> these names.)

<p><p>

<a name="%_sec_5.5.7"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.7">5.5.7&nbsp;&nbsp;Interfacing Compiled Code to the Evaluator</a></h3><p>


<a name="%_idx_6466"></a><a name="%_idx_6468"></a><a name="%_idx_6470"></a>
We have not yet explained how to load compiled code into the evaluator machine
or how to run it.  We will assume that the explicit-control-evaluator machine
has been defined as in section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>, with the
additional operations specified in footnote&nbsp;<a href="#footnote_Temp_809">38</a>.
We will implement
a procedure <a name="%_idx_6472"></a><tt>compile-and-go</tt> that compiles a Scheme expression, loads the
resulting object code into the evaluator machine,
and causes the machine to run the code in the
evaluator global environment, print the result, and
enter the evaluator's driver loop.  We will also modify the evaluator so that
interpreted expressions can call compiled procedures as well as interpreted
ones.  We can then put a compiled procedure into the machine and use the
evaluator to call it:<p>

<p><p><tt>(compile-and-go<br>
&nbsp;'(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n))))<br>
<i>&nbsp;;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>ok</i><br>
<i>&nbsp;;;;&nbsp;EC-Eval&nbsp;input:</i><br>
(factorial&nbsp;5)<br>
<i>;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>120</i><br>
</tt><p><p><p>


To allow the evaluator to handle compiled procedures (for example,
to evaluate the call to <tt>factorial</tt> above),
we need to change the code at <tt>apply-dispatch</tt>
(section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>) so that it recognizes
compiled procedures (as distinct from compound or primitive
procedures) and transfers control directly to the entry point of the
compiled code:<a name="call_footnote_Temp_833" href="#footnote_Temp_833"><sup><small>48</small></sup></a>
<p><p><tt><a name="%_idx_6474"></a>apply-dispatch<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;primitive-procedure?)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;primitive-apply))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;compound-procedure?)&nbsp;(reg&nbsp;proc))&nbsp;&nbsp;<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;compound-apply))<br>
&nbsp;&nbsp;(test&nbsp;(op&nbsp;compiled-procedure?)&nbsp;(reg&nbsp;proc))&nbsp;&nbsp;<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;compiled-apply))<br>
&nbsp;&nbsp;(goto&nbsp;(label&nbsp;unknown-procedure-type))<br>
<a name="%_idx_6476"></a>compiled-apply<br>
&nbsp;&nbsp;(restore&nbsp;continue)<br>
&nbsp;&nbsp;(assign&nbsp;val&nbsp;(op&nbsp;compiled-procedure-entry)&nbsp;(reg&nbsp;proc))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
</tt><p><p>
Note the restore of <tt>continue</tt> at <tt>compiled-apply</tt>.  Recall that the
evaluator was arranged so that at <tt>apply-dispatch</tt>, the continuation would
be at the top of the stack.  The compiled code entry point, on the other hand,
expects the continuation to be in <tt>continue</tt>, so <tt>continue</tt> must be
restored before the compiled code is executed.<p>


To enable us to run some compiled code when we start the evaluator
machine, we add a <tt>branch</tt> instruction at
the beginning of the evaluator machine, which causes the machine to
go to a new entry point if the <tt>flag</tt> register is set.<a name="call_footnote_Temp_834" href="#footnote_Temp_834"><sup><small>49</small></sup></a><p>


<p><p><tt>&nbsp;&nbsp;(branch&nbsp;(label&nbsp;external-entry))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;branches&nbsp;if&nbsp;<tt>flag</tt>&nbsp;is&nbsp;set</em><br>
read-eval-print-loop<br>
&nbsp;&nbsp;(perform&nbsp;(op&nbsp;initialize-stack))<br>
&nbsp;&nbsp;<tt>...</tt></tt><p><p>
<tt>External-entry</tt> assumes that the machine is started with
<tt>val</tt> containing the location of an instruction sequence that
puts a result into <tt>val</tt> and ends with <tt>(goto (reg
continue))</tt>.  Starting at this entry point jumps to the location designated
by <tt>val</tt>, but first assigns <tt>continue</tt> so that execution will return
to <tt>print-result</tt>, which prints the value in <tt>val</tt> and then goes to
the beginning of the evaluator's read-eval-print loop.<a name="call_footnote_Temp_835" href="#footnote_Temp_835"><sup><small>50</small></sup></a><p>


<p><p><tt><a name="%_idx_6482"></a>external-entry<br>
&nbsp;&nbsp;(perform&nbsp;(op&nbsp;initialize-stack))<br>
&nbsp;&nbsp;(assign&nbsp;env&nbsp;(op&nbsp;get-global-environment))<br>
&nbsp;&nbsp;(assign&nbsp;continue&nbsp;(label&nbsp;print-result))<br>
&nbsp;&nbsp;(goto&nbsp;(reg&nbsp;val))<br>
</tt><p><p>

Now we can use the following procedure to compile a procedure definition,
execute the compiled code, and run the read-eval-print loop so we can try the
procedure.  Because we want the compiled code to return to the location in
<tt>continue</tt> with its result in <tt>val</tt>, we compile the expression with a
target of <tt>val</tt> and a linkage of <tt>return</tt>.  In order to transform the
object code produced by the compiler into executable instructions for the
evaluator register machine, we use the procedure <tt>assemble</tt> from the
register-machine simulator (section&nbsp;<a href="book-Z-H-32.html#%_sec_5.2.2">5.2.2</a>).  We then initialize
the <tt>val</tt> register to point to the list of instructions, set the
<tt>flag</tt> so that the evaluator will go to <tt>external-entry</tt>, and start
the evaluator.<p>

<p><p><tt><a name="%_idx_6484"></a>(define&nbsp;(compile-and-go&nbsp;expression)<br>
&nbsp;&nbsp;(let&nbsp;((instructions<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(assemble&nbsp;(statements<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(compile&nbsp;expression&nbsp;'val&nbsp;'return))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eceval)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(set!&nbsp;the-global-environment&nbsp;(setup-environment))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(set-register-contents!&nbsp;eceval&nbsp;'val&nbsp;instructions)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(set-register-contents!&nbsp;eceval&nbsp;'flag&nbsp;true)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(start&nbsp;eceval)))<br>
</tt><p><p><p>

<a name="%_idx_6486"></a>If we have set up stack monitoring, as at the end of
section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>, we can examine the
stack usage of compiled code:<p>

<p><p><tt>(compile-and-go<br>
&nbsp;'(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n))))<br>
<br>
<i>(total-pushes&nbsp;=&nbsp;0&nbsp;maximum-depth&nbsp;=&nbsp;0)</i><br>
<i>&nbsp;;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>ok</i><br>
<i>&nbsp;;;;&nbsp;EC-Eval&nbsp;input:</i><br>
(factorial&nbsp;5)<br>
<i>(total-pushes&nbsp;=&nbsp;31&nbsp;maximum-depth&nbsp;=&nbsp;14)</i><br>
<i>;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>120</i><br>
</tt><p><p>
<a name="%_idx_6488"></a>Compare this example with the evaluation of <tt>(factorial 5)</tt> using
the interpreted version of the same procedure, shown at the end of
section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>.  The interpreted version required
144 pushes and a maximum stack depth of 28.  This illustrates the
optimization that results from our compilation strategy.<p>

<a name="%_sec_Temp_836"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_836">Interpretation and compilation</a></h4><p>

<a name="%_idx_6490"></a><a name="%_idx_6492"></a>
With the programs in this section, we can now experiment with the
alternative execution strategies of interpretation and
compilation.<a name="call_footnote_Temp_837" href="#footnote_Temp_837"><sup><small>51</small></sup></a>  An interpreter raises
the machine to the level of the user program; a compiler lowers the
user program to the level of the machine language.  We can regard the
Scheme language (or any programming language) as a coherent family of
abstractions erected on the machine language.  Interpreters are good
for interactive program development and debugging because the steps of
program execution are organized in terms of these abstractions, and
are therefore more intelligible to the programmer.  Compiled code can
execute faster, because the steps of program execution are organized
in terms of the machine language, and the compiler is free to make
optimizations that cut across the higher-level
abstractions.<a name="call_footnote_Temp_838" href="#footnote_Temp_838"><sup><small>52</small></sup></a><p>


The alternatives of interpretation and compilation also lead to
<a name="%_idx_6504"></a>different strategies for porting languages to new computers. Suppose
that we wish to implement Lisp for a new machine.  One strategy is
to begin with the explicit-control evaluator of section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4">5.4</a>
and translate its instructions to instructions for the
new machine.  A different strategy is to begin with the compiler and
change the code generators so that they generate code for the new
machine.  The second strategy allows us to run any Lisp program on
the new machine by first compiling it with the compiler running on our
original Lisp system, and linking it with a compiled version of the
run-time library.<a name="call_footnote_Temp_839" href="#footnote_Temp_839"><sup><small>53</small></sup></a>  Better yet, we can compile the compiler itself, and run
this on the new machine to compile other Lisp programs.<a name="call_footnote_Temp_840" href="#footnote_Temp_840"><sup><small>54</small></sup></a>  Or we can
compile one of the interpreters of section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a> to
produce an interpreter that runs on the new machine.<p>

<p><a name="%_thm_5.45"></a>
<b>Exercise 5.45.</b>&nbsp;&nbsp;<a name="%_idx_6506"></a><a name="%_idx_6508"></a>By comparing the stack operations used by compiled code to the stack
operations used by the evaluator for the same computation, we can
determine the extent to which the compiler optimizes use of the stack,
both in speed (reducing the total number of stack operations) and in
space (reducing the maximum stack depth).  Comparing this optimized
stack use to the performance of a special-purpose machine for the same
computation gives some indication of the quality of the compiler.<p>

<p><p>a. Exercise&nbsp;<a href="book-Z-H-34.html#%_thm_5.27">5.27</a> asked you to determine, as a function of
<em>n</em>, the number of pushes and the maximum stack depth needed by the
evaluator to compute <em>n</em>! using the recursive factorial procedure
given above.  Exercise&nbsp;<a href="book-Z-H-32.html#%_thm_5.14">5.14</a> asked you to do the same
measurements for the special-purpose factorial machine shown in
figure&nbsp;<a href="book-Z-H-31.html#%_fig_5.11">5.11</a>. Now perform the same analysis using the
compiled <tt>factorial</tt> procedure.<p>

Take the ratio of the number of pushes in the compiled version to the
number of pushes in the interpreted version, and do the same for the
maximum stack depth.  Since the number of operations and the stack
depth used to compute <em>n</em>! are linear in <em>n</em>, these ratios should
approach constants as <em>n</em> becomes large.  What are these constants?
Similarly, find the ratios of the stack usage in the special-purpose
machine to the usage in the interpreted version.<p>

Compare the ratios for special-purpose versus interpreted code to the ratios
for compiled versus interpreted code.  You should find that the
special-purpose machine does much better than the compiled code, since
the hand-tailored controller code should be much better than what is
produced by our rudimentary general-purpose compiler.<p>

<p><p>b. Can you suggest improvements to the compiler that would help it
generate code that would come closer in performance to the
hand-tailored version?

<p><p>

<p><a name="%_thm_5.46"></a>
<b>Exercise 5.46.</b>&nbsp;&nbsp;<a name="%_idx_6510"></a><a name="%_idx_6512"></a>Carry out an analysis like the one in
exercise&nbsp;<a href="#%_thm_5.45">5.45</a> to determine the effectiveness of
compiling the tree-recursive Fibonacci procedure<p>

<p><p><tt>(define&nbsp;(fib&nbsp;n)<br>
&nbsp;&nbsp;(if&nbsp;(&lt;&nbsp;n&nbsp;2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(fib&nbsp;(-&nbsp;n&nbsp;1))&nbsp;(fib&nbsp;(-&nbsp;n&nbsp;2)))))<br>
</tt><p><p>
compared to the effectiveness of using the special-purpose Fibonacci machine of
figure&nbsp;<a href="book-Z-H-31.html#%_fig_5.12">5.12</a>.  (For measurement of the interpreted
performance, see exercise&nbsp;<a href="book-Z-H-34.html#%_thm_5.29">5.29</a>.)
For Fibonacci, the time resource used is not linear in <em>n</em>; hence the
ratios of stack operations will not approach a limiting value that is
independent of <em>n</em>.
<p><p>

<p><a name="%_thm_5.47"></a>
<b>Exercise 5.47.</b>&nbsp;&nbsp;This section described how to modify the explicit-control evaluator so
that interpreted code can call compiled procedures.  Show how to
modify the compiler so that compiled procedures can call not only
primitive procedures and compiled procedures, but interpreted
procedures as well.  This requires modifying <tt>compile-procedure-call</tt>
to handle the case of compound (interpreted) procedures.
Be sure to handle all the same <tt>target</tt> and <tt>linkage</tt> combinations
as in <tt>compile-proc-appl</tt>.  To do the actual procedure application,
the code needs to jump to the evaluator's <tt>compound-apply</tt> entry point.
This label cannot be directly referenced in object code
(since the assembler requires that all labels referenced by the
code it is assembling be defined there), so we will add a register
called <tt>compapp</tt> to the evaluator machine to hold this
entry point, and add an instruction to initialize it:
<p><p><tt>&nbsp;&nbsp;(assign&nbsp;compapp&nbsp;(label&nbsp;compound-apply))<br>
&nbsp;&nbsp;(branch&nbsp;(label&nbsp;external-entry))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;branches&nbsp;if&nbsp;<tt>flag</tt>&nbsp;is&nbsp;set</em><br>
read-eval-print-loop<br>
&nbsp;&nbsp;<tt>...</tt></tt><p><p>
To test your code, start by defining a procedure <tt>f</tt> that calls a
procedure <tt>g</tt>.  Use <tt>compile-and-go</tt> to compile the definition
of <tt>f</tt> and start the evaluator.  Now, typing at the evaluator,
define <tt>g</tt> and try to call <tt>f</tt>.

<p><p>

<p><a name="%_thm_5.48"></a>
<b>Exercise 5.48.</b>&nbsp;&nbsp;<a name="%_idx_6514"></a>The <tt>compile-and-go</tt> interface implemented in this section is
awkward, since the compiler can be called only once (when the
evaluator machine is started).  Augment the compiler-interpreter
interface by providing a <tt>compile-and-run</tt> primitive that can be
called from within the explicit-control evaluator as follows:<p>

<p><p><tt><i>;;;&nbsp;EC-Eval&nbsp;input:</i><br>
(compile-and-run<br>
&nbsp;'(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1))&nbsp;n))))<br>
<i>;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>ok</i><br>
<i>;;;&nbsp;EC-Eval&nbsp;input:</i><br>
(factorial&nbsp;5)<br>
<i>;;;&nbsp;EC-Eval&nbsp;value:</i><br>
<i>120</i><br>
</tt><p><p>
<p><p>

<p><a name="%_thm_5.49"></a>
<b>Exercise 5.49.</b>&nbsp;&nbsp;As an alternative to using the explicit-control evaluator's
read-eval-print loop, design a register machine that performs a
read-compile-execute-print loop.  That is, the machine should run a
loop that reads an expression, compiles it, assembles and
executes the resulting code, and prints the result.  This is easy to
run in our simulated setup, since we can arrange to call the
procedures <tt>compile</tt> and <tt>assemble</tt> as ``register-machine
operations.''

<p><p>

<p><a name="%_thm_5.50"></a>
<b>Exercise 5.50.</b>&nbsp;&nbsp;<a name="%_idx_6516"></a>Use the compiler to compile the metacircular evaluator of
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a> and run this program using the register-machine
simulator.  (To compile more than one definition at a time, you can
package the definitions in a <tt>begin</tt>.)  The resulting interpreter
will run very slowly because of the multiple levels of interpretation,
but getting all the details to work is an instructive exercise.
<p><p>

<p><a name="%_thm_5.51"></a>
<b>Exercise 5.51.</b>&nbsp;&nbsp;<a name="%_idx_6518"></a>Develop a rudimentary implementation of Scheme in C (or some other
low-level language of your choice) by translating the explicit-control
evaluator of section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4">5.4</a> into C.  In order to run this code
you will need to also
provide appropriate storage-allocation routines and other run-time
support.

<p><p>

<p><a name="%_thm_5.52"></a>
<b>Exercise 5.52.</b>&nbsp;&nbsp;<a name="%_idx_6520"></a><a name="%_idx_6522"></a><a name="%_idx_6524"></a>As a counterpoint to exercise&nbsp;<a href="#%_thm_5.51">5.51</a>, modify the compiler
so that it compiles Scheme procedures into sequences of C
instructions.  Compile the metacircular evaluator of
section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a> to produce a Scheme interpreter written in C.

<p>
<p>



<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_794" href="#call_footnote_Temp_794"><sup><small>33</small></sup></a> This is a theoretical statement.  We are not claiming
that the evaluator's data paths are a particularly convenient or
efficient set of data paths for a general-purpose computer.  For example,
they are not very good for implementing high-performance floating-point
calculations or calculations that intensively manipulate bit vectors.

<p><a name="footnote_Temp_795" href="#call_footnote_Temp_795"><sup><small>34</small></sup></a> Actually, the machine that runs
compiled code can be simpler than the interpreter machine, because we
<a name="%_idx_6220"></a>won't use the <tt>exp</tt> and <tt>unev</tt> registers.  The interpreter
used these to hold pieces of unevaluated expressions.  With the
compiler, however, these expressions get built into the
compiled code that the register machine will run.  For the same
reason, <a name="%_idx_6222"></a>we don't need the machine operations that deal with expression
syntax.  But compiled code will use a few additional machine
operations (to represent compiled procedure objects) that didn't
appear in the explicit-control evaluator machine.

<p><a name="footnote_Temp_797" href="#call_footnote_Temp_797"><sup><small>35</small></sup></a> Notice, however, that our
compiler is a Scheme program, and the syntax procedures that it uses
to manipulate expressions are the actual Scheme procedures used with
the metacircular evaluator.  For the explicit-control evaluator, in
contrast, we assumed that equivalent syntax operations were available
as operations for the register machine.  (Of course, when we simulated
the register machine in Scheme, we used the actual Scheme procedures
in our register machine simulation.)

<p><a name="footnote_Temp_803" href="#call_footnote_Temp_803"><sup><small>36</small></sup></a> This procedure uses a feature of Lisp called <em><a name="%_idx_6280"></a><a name="%_idx_6282"></a><a name="%_idx_6284"></a><a name="%_idx_6286"></a><a name="%_idx_6288"></a><a name="%_idx_6290"></a>backquote</em> (or <em>quasiquote</em>) that is handy for constructing lists.
Preceding a list with a backquote symbol is much like quoting it,
except that anything in the list that is flagged with a comma is evaluated.<p>

For example, if the value of <tt>linkage</tt> is the symbol
<tt>branch25</tt>, then the expression
<tt>`((goto (label ,linkage)))</tt>
evaluates to the list
<tt>((goto (label branch25)))</tt>.
Similarly, if the value of <tt>x</tt> is the list <tt>(a b c)</tt>, then
<tt>`(1 2 ,(car x))</tt>
evaluates to the list
<tt>(1 2 a)</tt>.

<p><a name="footnote_Temp_806" href="#call_footnote_Temp_806"><sup><small>37</small></sup></a> We can't just
use the labels <tt>true-branch</tt>, <tt>false-branch</tt>, and
<tt>after-if</tt> as shown above,
because there might be more than one <tt>if</tt> in the program.
<a name="%_idx_6318"></a>The compiler uses the procedure <tt>make-label</tt> to generate labels.
<tt>Make-label</tt> takes a symbol as argument and returns a new symbol
that begins with the given symbol.  For example, successive calls to
<tt>(make-label 'a)</tt> would return <tt>a1</tt>, <tt>a2</tt>, and so on.
<tt>Make-label</tt> can be implemented similarly to the generation of
unique variable names in the query language, as follows:
<p><p><tt>(define&nbsp;label-counter&nbsp;0)<br>
<br>
(define&nbsp;(new-label-number)<br>
&nbsp;&nbsp;(set!&nbsp;label-counter&nbsp;(+&nbsp;1&nbsp;label-counter))<br>
&nbsp;&nbsp;label-counter)<br>
<br>
<a name="%_idx_6320"></a><a name="%_idx_6322"></a>(define&nbsp;(make-label&nbsp;name)<br>
&nbsp;&nbsp;(string-&gt;symbol<br>
&nbsp;&nbsp;&nbsp;&nbsp;(string-append&nbsp;(symbol-&gt;string&nbsp;name)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(number-&gt;string&nbsp;(new-label-number)))))<br>
</tt><p><p>


<p><a name="footnote_Temp_809" href="#call_footnote_Temp_809"><sup><small>38</small></sup></a> We need machine operations to implement a data
structure for representing compiled procedures, analogous to the structure for
compound procedures described in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.3">4.1.3</a>:
<p><p><tt><a name="%_idx_6332"></a>(define&nbsp;(make-compiled-procedure&nbsp;entry&nbsp;env)<br>
&nbsp;&nbsp;(list&nbsp;'compiled-procedure&nbsp;entry&nbsp;env))<br>
<br>
<a name="%_idx_6334"></a>(define&nbsp;(compiled-procedure?&nbsp;proc)<br>
&nbsp;&nbsp;(tagged-list?&nbsp;proc&nbsp;'compiled-procedure))<br>
<br>
<a name="%_idx_6336"></a>(define&nbsp;(compiled-procedure-entry&nbsp;c-proc)&nbsp;(cadr&nbsp;c-proc))<br>
<br>
<a name="%_idx_6338"></a>(define&nbsp;(compiled-procedure-env&nbsp;c-proc)&nbsp;(caddr&nbsp;c-proc))<br>
</tt><p><p>


<p><a name="footnote_Temp_812" href="#call_footnote_Temp_812"><sup><small>39</small></sup></a> Actually, we signal an error when the target is not <tt>val</tt>
and the linkage is <tt>return</tt>, since
the only place we request <tt>return</tt> linkages is in compiling
procedures, and our convention is that procedures return their
values in <tt>val</tt>.

<p><a name="footnote_Temp_813" href="#call_footnote_Temp_813"><sup><small>40</small></sup></a> Making a
<a name="%_idx_6356"></a>compiler generate tail-recursive code might seem like a
straightforward idea.  But most compilers for common languages,
including C and Pascal, do not do this, and therefore these languages
cannot represent iterative processes in terms of procedure call alone.
The difficulty with <a name="%_idx_6358"></a><a name="%_idx_6360"></a><a name="%_idx_6362"></a>tail recursion in these languages is that their
implementations use the stack to store procedure arguments and local
variables as well as return addresses.  The Scheme implementations
described in this book store arguments and variables in memory to be
garbage-collected.  The reason for using the stack for variables and
arguments is that it avoids the need for garbage collection in
languages that would not otherwise require it, and is generally
believed to be more efficient.  Sophisticated Lisp compilers can, in
fact, use the stack for arguments without destroying tail recursion.
(See <a name="%_idx_6364"></a>Hanson 1990 for a description.)  There is also some debate about
whether stack allocation is actually more efficient than garbage
collection in the first place, but the details seem to hinge on fine
points of computer architecture.  (See <a name="%_idx_6366"></a>Appel 1987 and <a name="%_idx_6368"></a><a name="%_idx_6370"></a>Miller and Rozas
1994 for opposing views on this issue.)

<p><a name="footnote_Temp_814" href="#call_footnote_Temp_814"><sup><small>41</small></sup></a> The variable
<a name="%_idx_6372"></a><tt>all-regs</tt> is bound to the list of names of all the registers:
<p><p><tt><a name="%_idx_6374"></a>(define&nbsp;all-regs&nbsp;'(env&nbsp;proc&nbsp;val&nbsp;argl&nbsp;continue))<br>
</tt><p><p>


<p><a name="footnote_Temp_815" href="#call_footnote_Temp_815"><sup><small>42</small></sup></a> Note that <tt>preserving</tt> calls <tt>append</tt> with three
<a name="%_idx_6396"></a>arguments.  Though the definition of <tt>append</tt> shown in this book
accepts only two arguments, Scheme standardly provides an <tt>append</tt>
procedure that takes an arbitrary number of arguments.

<p><a name="footnote_Temp_822" href="#call_footnote_Temp_822"><sup><small>43</small></sup></a> We have used
the same symbol <tt>+</tt> here to denote both the source-language
procedure and the machine operation.  In general there will not be a
one-to-one correspondence between primitives of the source language
and primitives of the machine.

<p><a name="footnote_Temp_823" href="#call_footnote_Temp_823"><sup><small>44</small></sup></a> Making the primitives into reserved
words is in general a bad idea, since a user cannot then rebind these
names to different procedures.  Moreover, if we add reserved words to
a compiler that is in use, existing programs that define procedures
with these names will stop working.  See
exercise&nbsp;<a href="#%_thm_5.44">5.44</a> for ideas on how to avoid this
problem.

<p><a name="footnote_Temp_824" href="#call_footnote_Temp_824"><sup><small>45</small></sup></a> This is not true if we allow
internal definitions, unless we scan them out.
See exercise&nbsp;<a href="#%_thm_5.43">5.43</a>.

<p><a name="footnote_Temp_826" href="#call_footnote_Temp_826"><sup><small>46</small></sup></a> This is the modification to variable lookup
<a name="%_idx_6446"></a><a name="%_idx_6448"></a>required if we implement the scanning method to eliminate internal
definitions (exercise&nbsp;<a href="#%_thm_5.43">5.43</a>).  We will need
to eliminate these definitions in order for lexical addressing to
work.

<p><a name="footnote_Temp_830" href="#call_footnote_Temp_830"><sup><small>47</small></sup></a> Lexical addresses cannot be used to access variables in the global
environment, because these names can be defined and redefined
interactively at any time.  With internal definitions scanned out, as
in exercise&nbsp;<a href="#%_thm_5.43">5.43</a>, the only definitions the
compiler sees are those at top level, which act on the global
environment.  Compilation of a definition does not cause the defined
name to be entered in the compile-time environment.

<p><a name="footnote_Temp_833" href="#call_footnote_Temp_833"><sup><small>48</small></sup></a> Of course, compiled procedures as well as interpreted
procedures are compound (nonprimitive).  For compatibility with
the terminology used in the explicit-control evaluator, in this
section we will use ``compound'' to mean interpreted (as opposed
to compiled).

<p><a name="footnote_Temp_834" href="#call_footnote_Temp_834"><sup><small>49</small></sup></a> Now that the evaluator machine starts
with a <tt>branch</tt>, we must always initialize the <tt>flag</tt> register
before starting the evaluator machine.  To start the machine at
its ordinary read-eval-print loop, we could use
<p><p><tt><a name="%_idx_6478"></a>(define&nbsp;(start-eceval)<br>
&nbsp;&nbsp;(set!&nbsp;the-global-environment&nbsp;(setup-environment))<br>
&nbsp;&nbsp;(set-register-contents!&nbsp;eceval&nbsp;'flag&nbsp;false)<br>
&nbsp;&nbsp;(start&nbsp;eceval))<br>
</tt><p><p>

<p><a name="footnote_Temp_835" href="#call_footnote_Temp_835"><sup><small>50</small></sup></a> Since a compiled procedure is an
object that the system may try to print, we also modify the system
print operation <tt>user-print</tt> (from section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>)
so that it will not attempt to print the
components of a compiled procedure:
<p><p><tt><a name="%_idx_6480"></a>(define&nbsp;(user-print&nbsp;object)<br>
&nbsp;&nbsp;(cond&nbsp;((compound-procedure?&nbsp;object)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(display&nbsp;(list&nbsp;'compound-procedure<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(procedure-parameters&nbsp;object)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(procedure-body&nbsp;object)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'&lt;procedure-env&gt;)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((compiled-procedure?&nbsp;object)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(display&nbsp;'&lt;compiled-procedure&gt;))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(display&nbsp;object))))<br>
</tt><p><p>


<p><a name="footnote_Temp_837" href="#call_footnote_Temp_837"><sup><small>51</small></sup></a> We can do even better by extending the compiler
to allow compiled code to call interpreted procedures.  See
exercise&nbsp;<a href="#%_thm_5.47">5.47</a>.

<p><a name="footnote_Temp_838" href="#call_footnote_Temp_838"><sup><small>52</small></sup></a> Independent of the strategy of execution, we
<a name="%_idx_6494"></a>incur significant overhead if we insist that errors encountered in
execution of a user program be detected and signaled, rather than being
allowed to kill the system or produce wrong answers.  For example, an
out-of-bounds array reference can be detected by checking the validity
of the reference before performing it.  The overhead of checking,
however, can be many times the cost of the array reference itself, and
a programmer should weigh speed against safety in determining whether
such a check is desirable.  A good compiler should be able to produce
code with such checks, should avoid redundant checks, and should allow
programmers to control the extent and type of error checking in the
compiled code.<p>

<a name="%_idx_6496"></a>Compilers for popular languages, such as C and C++,
put hardly any error-checking operations into
running code, so as to make things run as fast as possible.  As a
result, it falls to programmers to explicitly provide error checking.
Unfortunately, people often neglect to do this, even in
critical applications where speed is not a constraint.  Their programs
lead fast and dangerous lives.  For example, the notorious <a name="%_idx_6498"></a>``Worm''
that paralyzed the Internet in 1988 exploited the <a name="%_idx_6500"></a>UNIX<sup> <em>T</em><em>M</em></sup>
operating system's failure to check whether the input buffer has
<a name="%_idx_6502"></a>overflowed in the finger daemon. (See Spafford 1989.)

<p><a name="footnote_Temp_839" href="#call_footnote_Temp_839"><sup><small>53</small></sup></a> Of course, with either the
interpretation or the compilation strategy we must also implement for
the new machine storage allocation, input and output, and all the
various operations that we took as ``primitive'' in our discussion of
the evaluator and compiler.  One strategy for minimizing work here is
to write as many of these operations as possible in Lisp and then
compile them for the new machine.  Ultimately, everything reduces to a
small kernel (such as garbage collection and the mechanism for
applying actual machine primitives) that is hand-coded for the new
machine.

<p><a name="footnote_Temp_840" href="#call_footnote_Temp_840"><sup><small>54</small></sup></a> 
This strategy leads to amusing tests of correctness of
the compiler, such as checking
whether the compilation of a program on the new machine, using the
compiled compiler, is identical with the
compilation of the program on the original Lisp system.  Tracking
down the source of differences is fun but often frustrating, because
the results are extremely sensitive to minuscule details.

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-34.html">previous</a></span><span>, <a href="book-Z-H-36.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
